Brevet FR2880152A1 — publié le 20060630

La présente invention concerne un procédé pour l'optimisation de la gestion de fichiers à enregistrements. Elle a plus particulièrement pour but d'améliorer les performances relatives à la gestion de fichiers lorsque les enregistrements desdits fichiers sont stockés sur une mémoire persistante pour laquelle les opérations d'écriture sont coûteuses en temps d'exécution. Elle s'applique notamment mais non exclusivement au domaine de la carte à puce pour lequel les enregistrements sont écrits en mémoire non- volatile de 20 type EEPROM ou FlashROM. D'une manière générale, on sait que certains dispositifs, comme la carte à puce, disposent de mémoire persistante (par exemple EEPROM ou FlashROM) organisée en pages. Dans ces dispositifs, la gestion de fichiers utilise de la mémoire persistante pour stocker des fichiers, les données persistantes de chaque fichier sont constituées: o d'un descripteur de fichier qui contient des informations de structure comme, par exemple, l'identifiant du fichier, ses droits d'accès, le 30 nombre maximal d'enregistrements du fichier, la localisation en mémoire de l'espace réservé aux enregistrements du fichier, le nombre 2880152 -2 total d'enregistrements du fichier, la taille des différents enregistrements (ou la taille de chaque enregistrement si celle-ci est commune à tous les enregistrements), et la position du dernier enregistrement ajouté dans le cas d'un fichier cyclique; on appelle ces informations de manière générale des Informations de Gestion de Fichiers ou IGF . o du contenu des enregistrements dudit fichier; La gestion des enregistrements comme, par exemple, l'ajout d'un enregistrement à un fichier, peut nécessiter la modification de certaines informations des IGF (et donc du descripteur de fichier), comme le nombre d'enregistrements effectifs du fichier ou la position du dernier enregistrement ajouté dans le cas d'un fichier cyclique. Le descripteur de fichier est stocké dans une ou plusieurs pages différentes des pages servant au stockage du contenu des enregistrements. L'opération d'écriture d'une page étant coûteuse en temps d'exécution, il est 20 important, lors des mises à jour d'un fichier, de minimiser le nombre de pages à écrire. Dans ce but, l'invention propose un procédé selon lequel on fait en sorte que l'organisation en mémoire persistante des IGF et des enregistrements minimise le nombre d'écritures de pages lors d'opérations de modifications dudit fichier. Le procédé mis en oeuvre est basé ;sur une représentation de certaines informations de gestion de fichiers dits IGF telle qu'une partie de ces IGF puisse être inscrite dans des zones de mémoire contiguës aux enregistrements eux-mêmes (plutôt que regroupées, comme c'est le cas actuellement, dans le descripteur de fichier). Ce procédé selon l'invention comprend alors: a) l'inscription de certaines informations de gestion de fichiers, dites IGF, dans des zones de mémoire contiguës aux enregistrements du fichier; b) l'utilisation des IGF lors des opérations d'accès au fichier; c) la mise à jour de certaines IGF lors des opérations de modification de fichier. Avantageusement: - lesdits fichiers pourront consister en des fichiers cycliques et lesdites IGF pourront comporter des informations permettant de calculer la position du dernier enregistrement ajouté et/ou le nombre d'enregistrements effectifs et/ou la localisation en mémoire d'un enregistrement de fichier. - l'IGF associée à un enregistrement de position i dans le fichier pourra, dans le cas d'un fichier cyclique, comporter une information Inf[i] positionnée initialement à zéro et modifiée, lors de l'ajout d'un nouvel enregistrement à la position i en appliquant le calcul Inf[i] := 1 + (Inf[i] mod NmAx), NMax étant le nombre maximal d'enregistrements dans le fichier cyclique. - les enregistrements du fichier pourront être répartis en mémoire de sorte que la zone de mémoire contenant un enregistrement d'une taille t ne chevauche jamais plus de [(t/m)] pages physiques où m représente la taille d'une page physique et [(t/m)] désigne la plus petite valeur entière supérieure ou égale à t/m. - la lecture d'un enregistrement de numéro n pourra comporter l'utilisation des IGF pour calculer le nombre d'enregistrements du fichier et la position de l'enregistrement n. 2880152 4 - l'ajout d'un nouvel enregistrement pourra comporter l'utilisation des IGF pour calculer la position du prochain emplacement disponible - la mise à jour d'un enregistrement de numéro n pourra comporter l'utilisation des IGF pour calculer lie nombre d'enregistrements du fichier et la position de l'enregistrement n. - le support physique des fichiers pourra consister en une mémoire EEPROM, une mémoire Flash, un disque dur ou tout support permettant de sauvegarder les informations de manière permanente. Néanmoins, elle pourra consister en mémoire RAM ou tout support permettant de sauvegarder les informations de façon temporaire. Bien entendu l'invention concerne également un système pour la mise en oeuvre du procédé précédemment décrit ainsi que l'application dudit procédé et dudit système aux cartes à puce, aux téléphones cellulaires, aux assistants numériques personnels, aux terminaux de paiement bancaires ou aux terminaux de paiement portatifs. Des modes de mise en oeuvre du procédé selon l'invention seront décrits ci-après à titre d'exemples non limitatifs, avec référence aux dessins annexés 20 dans lesquels: - la figure 1 est une représentation schématique montrant l'organisation des données persistantes d'un fichier avant et après la mise en oeuvre du procédé selon l'invention. - Les figures 2 à 8 sont des représentations mémoire, les figures 2 à 4 étant des représentations optimales. On rappelle tout d'abord qu'un fichier à enregistrements est composé d'un ensemble d'enregistrements qui peuvent être accédés de façon aléatoire. On distingue deux types de fichiers à enregistrements, les fichiers linéaires et les fichiers cycliques (aussi appelés fichiers circulaires). La taille d'un 2880152 5 enregistrement peut être soit fixe soit variable (dans le deuxième cas, chaque enregistrement du fichier peut donc avoir une taille différente). Lors de la création d'un fichier, on indique typiquement le nombre maximal d'enregistrements que peut contenir le fichier et l'espace maximal de mémoire persistante réservé au stockage des enregistrements du fichier. Lorsque le fichier contient des enregistrements de taille fixe, l'espace maximal réservé aux enregistrements du fichier peut être déduit facilement du nombre maximal d'enregistrements. Chaque enregistrement du fichier est identifié par un numéro compris entre 1 et N, où N désigne le nombre d'enregistrements du fichier. Dans un fichier linéaire, les enregistrements sont numérotés séquentiellement depuis 1 au fur et à mesure de leur ajout. Dans un fichier cyclique, le dernier enregistrement ajouté est toujours numéroté 1 (l'ancien enregistrement 1, s'il existait, est alors renuméroté 2). A titre d'exemple, les principales opérations relatives aux fichiers à enregistrements sont décrites dans la norme ISO/IEC 7816-4 lorsque le 20 domaine d'application est la carte à puce: É La lecture de l'enregistrement numéro n (commande READ RECORD); É L'ajout d'un nouvel enregistrement (commande APPEND RECORD); É La mise à jour de l'enregistrement numéro n (commandes WRITE RECORD et UPDATE RECORD). Les données du fichier sont constituées: É d'un descripteur de fichier global, qui contient typiquement des informations fixes du fichier: o identifiant du répertoire contenant le fichier; o identifiant(s) du fichier; 2880152 6 o localisation en mémoire persistante de l'espace réservé pour les structures de données d'enregistrement, notée LocBase; o droit d'accès; o etc. É d'un ensemble de structures de données d'enregistrement composées chacune: o d'un descripteur partiel d'enregistrement; o du contenu de l'enregistrement; Dans l'exemple représenté sur la figure 1, la colonne de gauche montre l'organisation des données persistantes d'un fichier selon la technique classique dans lequel le descripteur global 1 contient des données fixes 2 et des données variables 3 tandis que l'espace réservé aux enregistrements 4 ne contient que des données d'enregistrement 5 à 9. Par contre, la colonne de gauche montre une organisation conforme à l'invention dans lequel le descripteur global 11 contient en plus des données fixes 12, un volume réduit de données variables 13 tandis que l'espace réservé aux enregistrements 14 contient en plus des données d'enregistrement 15 à 19, des Informations de Gestion Réparties (IGR) 15' à 19'. Ainsi le procédé selon l'invention permet avantageusement de mettre en oeuvre les opérations sur les enregistrements qui nécessitent des modifications de ces IGR sans écriture supplémentaire dans les pages du descripteur global: les IGR étant contenues dans les mêmes pages que les enregistrements, seules ces pages doivent être modifiées. L'espace réservé aux structures de données d'enregistrements est constitué d'un ensemble de pages contiguës en mémoire persistante. L'objet du présent brevet concerne les données de cet espace. Dans un pseudo-language de 2880152 7 programmation, la structure de données d'enregistrement peut s'écrire de la façon suivante: record { descriptor { // Descripteur partiel d'enregistrement inf; // Information attachée à l'enregistrement // Contenu de l'enregistrement Le stockage en mémoire persistante des structures de données 15 d'enregistrement dépend de la taille d'une page. Si les tailles de la structure de données d'enregistrement (dans l'hypothèse où les enregistrements sont de taille fixe) et d'une page sont dans un rapport entier, il existe une représentation mémoire optimale. Dans la figure 2, la taille de la structure de données d'enregistrement est identique à celle d'une page. Dans la figure 3, la taille de la structure de données d'enregistrement est deux fois plus grande que celle d'une page. Dans la figure 4, la taille de la structure de données d'enregistrement est deux fois plus petite que celle d'une page. Si les tailles de la structure de données d'enregistrement (dans l'hypothèse où les enregistrements sont de taille fixe) et d'une page ne sont pas dans un rapport entier, ou si les enregistrements ne sont pas de taille fixe, l'une des représentations mémoire suivantes peut être utilisée. 2880152 8 Dans les figures 5 et 6, la taille de la structure de données d'enregistrement est considérée comme fixe et supérieure à celle d'une page sans toutefois être multiple de la taille d'une page. Dans la figure 5, chaque structure de données d'enregistrement est alignée sur un début de page, ce qui introduit une perte d'espace (matérialisée par des hachures) entre chaque structure de données d'enregistrement. Dans la figure 6, les structures de données d'enregistrement sont organisées pour minimiser le nombre de pages utilisées pour le stockage. Dans la figure 7, la structure de données d'enregistrement numéro 2 (Rec#2) est à cheval sur 2 pages alors la longueur de cet enregistrement est inférieure à 1 page. Dans la figure 8, la structure de données d'enregistrement numéro 2 (Rec#2) est à cheval sur 3 pages alors que la longueur de cet enregistrement est comprise entre 1 et 2 pages. Ces représentations mémoire ne sont pas optimales car la mise à jour de la structure de données d'enregistrement induit une écriture de page en plus que strictement nécessaire. Dans ces cas de figure, la représentation mémoire de la figure 5 doit être préférée. Pour décrire la mise en oeuvre du procédé, on prend à titre d'exemple un fichier cyclique fixe dont le nombre maximal d'enregistrements est NmAx=3 et dont la taille de la structure de données d'enregistrement est identique à celle d'une page. Le principe est généralisable à des fichiers cycliques fixes de taille arbitraire. On note: É NmAx, le nombre maximal d'enregistrements dans le fichier cyclique; É N, le nombre d'enregistrements écrits dans le fichier cyclique ( 0 N Npx); 2880152 9 É Rec[i], la structure de données d'enregistrement numéro i: (0 i N; É PNEÇT, la position absolue à l'intérieur du fichier cyclique de prochain enregistrement à ajouter (0 PNEXT On suppose que la zone de mémoire persistante est initialement à zéro, ce qui implique que la valeur de Rec[i].Inf vaut zéro pour les enregistrements non encore occupés. Le tableau 1 ci-après montre l'état d'un fichier cyclique après ajouts successifs 20 d'enregistrements. 2880152 - 10 - Etat: (0) (1) (2) (3) (4) Rec# indéf. 1 2 3 1 2 3 1 2 3 1 2 3 Inf[0] 0 1 1 1 2 2 2 3 3 3 1 1 1 Rec# indéf. indéf. 1 2 3 1 2 3 1 2 3 1 2 Inf[1] 0 0 1 1 1 2 2 2 3 3 3 1 1 Rec# indéf. indéf. indéf. 1 2 3 1 2 3 1 2 3 1 Inf[2] 0 0 0 1 1 1 2 2 2 3 3 3 1 NmAx 3 3 3 3 3 3 3 3 3 3 3 3 3 N 0 1 2 3 3 3 3 3 3 3 3 3 3 S 0 1 2 3 4 5 6 7 8 9 7 5 3 PNEXT 0 1 2 0 1 2 0 1 2 0 1 2 0 PREcl indéf. 0 1 2 0 1 2 0 1 2 0 1 2 PjpC2 indéf. indéf. 0 1 2 0 1 2 0 1 2 0 1 PREC3 indéf. indéf. indéf. 0 1 2 0 1 2 0 1 2 0 Le tableau 1 donne les valeurs des Inf[i], Nom, N, S, PNEXT et des PREc, pour un fichier cyclique initialement vide et contenant NMAx=3 enregistrements au maximum. Les valeurs en gras indiquent la nouvelle valeur prise par Inf[i] lors de l'ajout d'un nouvel enregistrement, selon l'équation 1, ci après calcul de Inf[i] lors de l'ajout d'un nouvel enregistrement: Inf[i] := 1 + (Inf[i] mod Nom) Initialement, dans l'état (0), le fichier cyclique est vide. Le nombre d'enregistrements N vaut 0 et les trois positions (absolues) 0, 1 et 2 du fichier cyclique sont disponibles. La prochaine position disponible PNEXT pour un ajout d'enregistrement est la position O. Dans l'état (1), après ajout du premier enregistrement à la position 0, le nombre d'enregistrements N vaut 1 et les deux positions (absolues) 1 et 2 du fichier cyclique sont disponibles. La position absolue PREC1 de l'enregistrement numéro 1 vaut 0 et la prochaine position disponible PNEXT pour un ajout d'enregistrement est la position 1. Dans l'état (2), après ajout du deuxième enregistrement à la position 1, le nombre d'enregistrements N vaut 2 et la position 2 du fichier cyclique est disponible. La position PREC1 de l'enregistrement numéro 1 vaut 1, celle PREC2 de l'enregistrement numéro 2 vaut 0, et la prochaine position disponible PNEXT pour un ajout d'enregistrement est la position 2. Dans l'état (3), après ajout du troisième enregistrement à la position 2, le nombre d'enregistrements N vaut 3 et toutes les positions du fichier cyclique sont occupées. La position PREC1 de l'enregistrement numéro 1 vaut 2, celle PREC2 de l'enregistrement numéro 2 vaut 1, celle PREC3 de l'enregistrement numéro 3 vaut 0, et la prochaine position disponible PNEXT pour un ajout d'enregistrement est la position 0. Dans la mise en oeuvre du procédé, à chaque emplacement de structure de données d'enregistrement Rec[i] (avec 0 Le nombre d'enregistrements du fichier est déterminé grâce à l'équation 3 suivante: Si S NmAx, alors N:= NmAx La position du prochain enregistrement disponible est déterminée grâce à l'équation 4 suivante: PNEXT:= S mod NmAx La position de l'enregistrement numéro n (avec 1 La Localisation de l'emplacement des données de l'enregistrement de position i est donnée par l'équation 6 ci-après: Loci:= LocBase + i * LREC (avec 0 Initialement, le fichier est soit vide (c'est à dire qu'il ne contient aucun enregistrement), soit non vide (c'est à dire qu'il contient au moins un enregistrement). Quel que soit l'état initial du fichier cyclique, les informations attachées aux enregistrements initiaux du fichier (Inf[i]) doivent être celles de l'une des configurations décrites dans le tableau 1. La lecture de l'enregistrement consiste tout d'abord à vérifier la validité de n, 20 ensuite à localiser l'emplacement des données de l'enregistrement numéro n, enfin de lire les données ainsi localisées. Paramètre d'entrée: É n, numéro de l'enregistrement à lire Paramètre de sortie: É Données de l'enregistrement numéro n Conditions d'erreur: É Paramètre n invalide 2880152 - 14- La lecture de l'enregistrement numéro n peut s'effectuer selon l'algorithme suivant: É Calculer la quantité S, selon l'équation 2; É Calculer le nombre d'enregistrements du fichier, N, selon l'équation 3; É Si n ne satisfait pas 1 Paramètre d'entrée: É n, numéro de l'enregistrement à mettre à jour (n > 0) É data, données à mettre à jour Paramètre de sortie: É néant Conditions d'erreur: É Paramètre n invalide É Longueur des données invalide La mise à jour de l'enregistrement numéro n peut s'effectuer selon l'algorithme suivant: É Calculer la quantité S, selon l'équation 2; É Calcul du nombre d'enregistrements du fichier, N, selon l'équation 3; É Si n ne satisfait pas 1 -17-Revendications 1. Procédé de gestion de fichiers à enregistrements sur des supports physiques caractérisé en ce qu'il comprend: a) l'inscription de certaines informations de gestion de fichiers, dites IGR, dans des zones de mémoire contiguës aux enregistrements du fichier; b) l'utilisation des IGR lors des opérations d'accès au fichier; c) la mise à jour de certaines IGR lors des opérations de modification de fichier. 2. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 1, caractérisé en ce que lesdits fichiers sont des fichiers cycliques et lesdites IGR comportent des informations permettant de calculer la position du dernier enregistrement ajouté et/ou le nombre d'enregistrements effectifs et/ou la localisation en mémoire d'un enregistrement du fichier. 3. Procédé de gestion de fichiers à enregistrements sur des supports 20 physiques selon la revendication 2, caractérisé en ce que l'IGR associée à un enregistrement de position i dans le fichier comporte une information Infli] positionnée initialement à zéro et modifiée, lors de l'ajout d'un nouvel enregistrement à la position i en appliquant le calcul Inf[i] := 1 + (Inf[i] mod Nom), NmAx étant le nombre maximal d'enregistrements dans le fichier cyclique. 4. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 3, caractérisé en ce que le nombre d'enregistrements effectif dans le fichier est 30 calculé en appliquant l'équation suivante: 2880152 - 18- Si S NmAx, alors N:= NmAx la valeur S étant calculée en appliquant l'équation suivante: i Inf [ i] o 5. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 3, caractérisé en ce que la position du prochain enregistrement disponible est calculée en appliquant l'équation suivante: PNEXT S mod NmAx 6. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 3, caractérisé en ce que la position de l'enregistrement de numéro n est calculée en appliquant l'équation suivante. PRECn:_ (S n) mod NmAx 7. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 1, caractérisé en ce que les enregistrements du fichier sont répartis en mémoire de sorte que la zone de mémoire contenant un enregistrement d'une taille t ne chevauche jamais plus de [(t/m)] pages physiques où m représente la taille d'une page physique et [(t/m)] désigne la plus petite valeur entière supérieure ou égale à t/m. 2880152 -19- 8. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 1, caractérisé en ce qu'une opération de lecture d'un enregistrement de numéro n comporte l'utilisation des IGR pour calculer le nombre d'enregistrements du 5 fichier et la position de l'enregistrement n. 9. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 1, caractérisé en ce qu'une opération d'ajout d'un nouvel enregistrement 10 comporte l'utilisation des IGR pour calculer la position du prochain emplacement disponible. 10. Procédé de gestion de fichiers à enregistrements sur des supports physiques selon la revendication 1, caractérisé en ce qu'une opération de mise à jour d'un enregistrement de numéro n comporte l'utilisation des IGR pour calculer le nombre d'enregistrements du fichier et la position de l'enregistrement n. 11. Procédé de gestion de fichiers à enregistrements sur des supports 20 physiques selon la revendication 3, caractérisé en ce qu'une opération de lecture d'un enregistrement de numéro n comporte les étapes suivantes: Calcul de la quantité S, selon l'équation suivante: i Nom, alors N:= NmAx É Si n ne satisfait pas 1 NmAx, alors N:= NMAx É Si n ne satisfait pas 1 15. Procédé de gestion de fichiers cyclique à enregistrements sur des 20 supports physiques selon la revendication 1, caractérisé en ce le support physique des fichiers est une mémoire RAM ou tout support permettant de sauvegarder les informations de manière temporaire. 16. Système assurant la gestion de fichiers à enregistrements sur des supports conformément au procédé selon l'une des revendications précédentes. 17. Application du procédé selon l'une quelconque des revendications 30 1 à 15, à une carte à puce, à un téléphone cellulaire, à un assistant numérique 2880152 - 23 - personnel, à un terminal de paiement bancaire ou à un terminal de paiement portatif. 18. Application du système selon la revendication 16, à une carte à 5 puce, à un téléphone cellulaire, à un assistant numérique personnel, à un terminal de paiement bancaire ou à un terminal de paiement portatif.