Brevet FR2929423A1 — publié le 20091002

DISPOSITIF DE SECURISATION DE FILES D'ATTENTE EN MEMOIRE La présente invention s'applique au domaine des mémoires tampons associées à des calculateurs, plus particulièrement lorsque lesdits calculateurs doivent exécuter des processus partageant une mémoire de ce type. C'est notamment le cas dans les dispositifs de communication où il est fréquent d'utiliser des dispositifs files d'attentes pour tamponner l'écoulement de plusieurs flux convergents de tâches à produire vers un ou plusieurs dispositifs serveurs exécutant lesdites tâches. Une modalité classique de gestion des accès mémoires par les différents processus est de séquencer ceux-ci de manière cyclique. Selon cette modalité, les processus écrivent et lisent dans la ou les mémoires tampon les données qu'ils produisent et utilisent dans un ordre donné. Des mémoires tampons couramment utilisées vont par exemple être du type First ln First Out (FIFO ou Premier entré premier sorti), c'est-à-dire que la première donnée traitée par une séquence d'écriture sera également la première donnée traitée par la séquence de lecture qui doit utiliser les données de la mémoire. Il peut également arriver que l'on ait à simuler un processus de type FIFO. Dans les deux cas de fonctionnement réél ou simulé, chaque donnée à lire est repérée par l'adresse où elle a été écrite. Dans des systèmes de calcul de ce type, il est donc important d'assurer la fiabilité du processus de gestion des mémoires tampon de manière à pouvoir garantir que la donnée que l'on accède en lecture est bien celle correspondant au processus qui doit la traiter. Cet objectif de fiabilité est particulièrement important dans les systèmes de calcul à haute criticité, tels que ceux embarqués sur aéronef. Or les pointeurs et compteurs d'entrées/sorties de la mémoire qui sont utilisés dans l'art antérieur pour gérer les flux de données à lire sont sujets à des pannes pouvant par exemple provoquer la détection d'une situation de FIFO vide erronée, ce qui entraîne la perte d'une tâche à effectuer, ladite perte n'étant pas détectée. Ce problème général de vérification de l'intégrité d'un compteur de séquence est résolu par le procédé divulgué par le brevet européen EP 0 694 842 appartenant à la demanderesse, dans lequel sont détectées des erreurs dans le déroulement d'une séquence linéaire d'ordres stockés sous forme de mots dans une série de cases mémoires, l'association entre ordres et cases mémoires étant codée au moment de l'écriture et vérifiée au moment de la lecture, ce qui permet de vérifier que la donnée est bien lue dans la bonne case. Ce procédé appliqué aux ordres à séquence linéaire n'est pas directement transposable au procédé de gestion des entrées/sorties d'une FIFO qui est cyclique. Pour pouvoir l'appliquer, ce qui présente des avantages explicités plus loin dans la présente description, il est nécessaire de prévoir un codage spécifiquement adapté pour ce procédé cyclique. C'est l'objet de la présente invention. A cet effet, ladite invention divulgue un dispositif de gestion des accès à un module de stockage de données comprenant au moins une mémoire dont au moins un espace est géré de manière à produire une fonctionalité de type FIFO, ledit dispositif comprenant au moins une paire de pointeurs des accès en écriture et en lecture à ladite mémoire et au moins un module de génération d'au moins un code séquentiel dont une partie de séquence est écrite en même temps que chaque donnée, et de lecture et de vérification dudit code, caractérisé en ce que chaque code séquentiel généré est caractéristique de l'espace dans lequel la donnée est écrite.. Avantageusement, ledit code séquentiel est combiné avec une parité calculée sur la donnée. Avantageusement, le code caractéristique de l'espace dans lequel la donnée est écrite est constitué par une séquence périodique de bits dont la période ne divise pas de façon entière le nombre de mots correspondant à la taille dudit espace. Avantageusement, la distance d'auto-ambiguïté du code séquentiel est minimale. Avantageusement, la somme des distances d'ambiguïté entre les codes 30 séquentiels distincts appliqués à plusieurs mémoires adjacentes dudit module prises deux à deux est minimale. La présente invention divulgue également un procédé de gestion des accès à un module de stockage de données comprenant au moins une mémoire dont au moins un espace est géré de manière à produire une fonctionalité de 35 type FIFO, ledit procédé comprenant au moins une étape de pointage des accès en écriture et en lecture à ladite mémoire et au moins une étape de génération d'un code séquentiel, dont une partie de séquence est écrite en même temps que chaque donnée, et de lecture et de vérification dudit code, caractérisé en ce que chaque code généré est caractéristique de l'espace dans lequel la donnée est écrite . En outre, le dispositif de la présente invention offre l'avantage d'être peu coûteux, le nombre de bits de codage augmentant comme le logarithme de la taille de la mémoire, comme il sera montré plus loin. L'invention sera mieux comprise et ses différentes caractéristiques et avantages ressortiront de la description qui suit de plusieurs exemples de réalisation et de ses figures annexées dont : La figure 1 est un schéma de FIFO avec génération d'un code selon l'invention ; La figure 2 est un exemple de table de calcul de critère du choix du code selon l'invention. La figure 1 représente un dispositif de stockage de données comprenant des mémoires de type FIFO. Dans cet exemple de réalisation, on illustre un cas de deux mémoires FIFO 10 gérées par un même dispositif. Un des aspects de l'invention est en effet de choisir des codes qui puissent coexister. Chacune des mémoires est représentée à la fois en écriture (à gauche sur la figure) et en lecture (à droite sur la figure). Traditionnellement, la gestion des accès mémoires est effectuée par deux pointeurs, un pointeur PE', PE2 210 d'écriture et un pointeur PL', PL2 220 de lecture. Ces pointeurs comprennent les adresses des cases mémoires qui doivent être respectivement écrites et lues. PE', PE2 s'incrémentent à chaque ajout d'un élément dans la file d'attente, PL', PL2 poursuivent les pointeurs d'écriture en s'incrémentant à chaque consommation d'un élément par l'un des serveurs de tâches. L'état FIFO non vide découle d'une différence entre les pointeurs. L'état FIFO vide est atteint lorsque l'égalité entre les deux pointeurs est obtenue lors d'une incrémentation du pointeur de lecture. Le terme � incrémentation � doit être ici pris dans un sens particulier qui diffère légèrement de la définition arithmétique générale. En effet l'incrémentation est normalement une opération sur l'ensemble des nombres entiers et par conséquent est définie sur un domaine infini. Il ne peut pas en être ainsi dans un dispositif matériel et l'on est contraint de définir pour chaque pointeur PE et PL une valeur minimale Vm et une valeur maximale VM, avec comme convention pour l'incrémentation des pointeurs d'être identique à l'incrémentation arithmétique pour toutes les valeurs de pointeurs différentes de VM, tandis que VM+1 = Vm. Ainsi on définit une opération d'incrémentation sur un ensemble fermé constitué par l'intervalle des entiers [Vm, VM]. Le caractère fini de l'espace mémoire associé à une FIFO implique l'existence d'un état � FIFO pleine � qui découle de l'égalité entre le pointeur de lecture et la prochaine valeur du pointeur d'écriture. En général, on détecte à ce stade une telle situation de remplissage extrème de la FIFO et on interdit une incrémentation ultérieure qui correspondrait à une situation d'overflow ou débordement. On peut remarquer que le nombre de mots contenus dans la FIFO peut être obtenu par la différence (modulo VM-Vm) entre PE et PL. Ainsi lorque VMVm est une puissance N de deux, il est aisé de connaître le remplissage instantané de la FIFO en extrayant les N bits de poid faible de la différence PE-PL. Lorsque cette condition n'est pas réunie, le calcul du nombre de mots instantanément contenu dans la FIFO est beaucoup plus complexe et coûteux à réaliser en nombre de portes logiques et on a alors avantageusement recours à un compteur/décompteur C/D 20 indépendant qui s'incrémente à chaque écriture et se décrémente à chaque lecture. Dans ce cas la situation de FIFO vide correspond à la valeur 0 de ce compteur/décompteur C/D tandis que la situation de FIFO pleine correspond à la valeur C/D = VM-Vm. Quoi qu'il en soit, l'existence de trois compteurs indépendants par FIFO n'est pas gratuite et si l'on doit gérer de façon multiplexée plusieurs FIFO dans un même espace mémoire, c'est autant de pointeurs qu'il faut multiplexer pour produire l'adresse d'accès en lecture et/ou en écriture à la mémoire, ainsi que le statut de remplissage de la FIFO en cours de traitement. La complexité structurelle est un handicap, certes à relativiser si l'on considère l'augmentation constante des capacités d'intégration des technologies électroniques. En revanche, dans les applications à haut niveau de contraintes sécuritaires, les défaillances de ces dispositifs sont particulièrement gênantes car susceptibles de provoquer des modes de pannes particulièrement redoutés et ce d'autant plus qu'ils sont généralement non systématiquement détectés ce qui altère le niveau de confiance. Les principaux types de pannes sont les suivants: - perte indétectée d'une tâche à effectuer soit par une panne du compteur/ décompteur provoquant la détection d'une situation de FIFO vide alors qu'elle n'est pas encore atteinte, soit par altération ou collage d'un bit d'un pointeur ; � babbling � ou bégaiement soit en raison d'une panne du compteur/ io décompteur provoquant la non détection d'une situation de FIFO vide alors qu'elle est atteinte, soit en raison de l'altération ou du collage d'un bit d'un pointeur ; dans ce deuxième cas, on voit que perte de tâche et babbling vont de pair, le nombre de tâches traitées étant inchangé mais certaines tâches n'étant jamais traitées, tandis que 15 d'autres le sont plusieurs fois ; � impersonation � correspondant à l'écrasement d'une tâche d'une FIFO par une écriture à une adresse erronnée d'une donnée destinée à une autre FIFO ou à la lecture à une adresse erronnée dans une autre FIFO ; là encore, ce mode de panne s'accompagnera également 20 de perte non detectée. Ces modes de panne non détectées sont notamment très préjudiciables à la certification de réseaux de communications critiques pour lesquels la qualité de service doit être garantie ou la perte de service détectée de manière certaine et rapide. 25 Pour assurer la sécurisation de l'exécution d'une séquence linéaire d'instructions, il est connu de EP 0 694 842 de coder lesdites instructions par une séquence correspondante de mots d'un ou plusieurs bits à l'écriture et de vérifier que cette séquence est présente à l'identique à la lecture. Or, la 30 suite des valeurs prises par un pointeur d'écriture de FIFO peut être considérée comme une séquence linéaire dans la mesure où elle est obtenue par une suite indéfinie d'incrémentations. De la même façon, le pointeur de lecture de la FIFO est assujetti à parcourir de façon différée dans le temps la même séquence de valeurs représentant les adresses successives des tâches à exécuter dans l'ordre exact où elles ont été placées dans la FIFO . Selon l'invention, des mots mil, m'2, m'3, m';..., d'un bit ou plus, appartenant à une suite caractéristique de la FIFO, sont ajoutés respectivement aux données di, d2, D3, D'i...par un module de génération 30 au moment de leur écriture dans les cases mémoires correspondantes sur lesquelles pointe successivement PE. Au moment de la lecture, le module vérifie l'identité de la suite {m';} à la suite {m;} en utilisant un comparateur logique. En cas d'écart, la donnée est rejetée. io Pour garantir la détection de toute défaillance de l'un quelconque des pointeurs, il suffit donc de coder au moins un bit de la donnée écrite dans la FIFO avec une séquence de 1 et de 0 représentative de la FIFO considérée. On prendra soin de faire en sorte que chaque FIFO possède une signature invariante et spécifique constituée par une séquence privée qui sera produite 15 lors de l'ecriture des mots en FIFO puis vérifiée lors de la lecture des mots préalablement inscrits. Ainsi, si l'ordre de lecture des données diffère de celui d'écriture le taux de détection de la défaillance croîtra exponentiellement avec le nombre de manquement à la séquence correcte. Ainsi avec un seul bit par mot pour coder la séquence, le premier manquement est détecté à 20 50%. Au second manquement, on a déjà détecté 75% des erreurs. Au troisième 87,5% ... au dixième, plus de 99,9% et au vingtième plus de 99, 99999%. On remarque par ailleurs que les défaillances affectant le contenu de la mémoire et les défaillances affectant l'adressage sont à priori indépendantes. 25 En combinant par un OU EXCLUSIF une parité sur la donnée avec le bit de codage issu de la séquence de bits représentative de la FIFO considérée, on peut également détecter en sortie de cette porte les erreurs de données. II convient maintenant de décrire les modalités de choix de la séquence de 30 codage propre à chaque FIFO. Ce choix doit être opéré en tenant compte du nombre, de la taille et de l'adjacence des espaces mémoires auxquels on aura conféré une fonctionalité de FIFO. Le code optimal sera choisi en fonction de ces paramètres. II est préférentiellement périodique et non aléatoire. Un certain nombre de précautions doivent être prises pour éviter 35 des défaillances classiques. Tout d'abord, il est judicieux de choisir pour chaque séquence de bits représentatifs d'une FIFO, une séquence périodique dont la période ne divise pas de façon entière le nombre de mots de l'espace mémoire correspondant de la FIFO considérée. Ainsi tout débordement en lecture par manquement à détecter la situation de FIFO vide, provoquera de manière certaine la détection de la défaillance à l'issue d'un nombre de lectures strictement inférieur à la période de la séquence. En effet, dans un tel cas, le dispositif de contrôle en lecture détectera une rupture par rapport à la séquence attendue. Le dispositif correspondant est relativement peu coûteux car, pour une séquence de période P, il consiste à ajouter N bits à chaque pointeur avec 2" > P. Ces N bits étant utilisés pour coder les états du séquenceur générant la dite séquence. Il est possible de définir un certain nombre de règles que doivent 15 préférentiellement observer les séquences : On fait tout dabord remarquer que pour être périodique, une séquence de 1 et de 0 doit comporter un nombre pair de transitions par période Par ailleurs on éliminera les séquences triviales de période 1 constituées d'une succession de 1 ou d'une succession de 0 qui sont sans intérêt dans 20 notre cas. La première des règles suivante apparaît donc comme une évidence : les schémas de 1 et de 0 d'une séquence présentent un nombre pair non nul de transitions par période ; - deux séquences qui se déduisent l'une de l'autre par décalage ne sont 25 que deux avatars d'une même séquence et ne doivent pas coexister dans le même dispositif de gestion de FIFO comme étant caractéristiques de deux fifos distinctes ; - en revanche deux séquences dissymétriques qui se déduisent l'une de l'autre par inversion de polarité peuvent coexister. 30 - on évite dans la mesure du possible les séquences de période correspondant à une puissance de 2 car elles sont susceptibles d'être prises en défaut par une défaillance simple (collage) d'un bit d'adresse unique. Le respect de ces règles permet de définir des listes de séquences qui peuvent être utilisées dans un même système de gestion de plusieurs FIFO: - séquences de période 3 : 001, 110 - séquences de période 5 : 00001, 11110, 00011, 11100, 00101, 11010 - séquences de période 6 : 000001, 111110, 000011, 111100, 111000, 001101, 110010, 000101, 111010, 101010 Séquences de période 7 : 0000001, 1111110, 0000011, 1111100, 0000111, 1111000, 0011001, 1100110, 0001001, 1110110, 0001011, 1110101, 0001101, 1110010, 0000101, 1111010, 0010101, 1101010 Les séquences ci-dessus ont des représentations dites canoniques : elles se caractérisent par le fait qu'elles commencent toujours par la séquence de bits identiques la plus longue et par conséquent se terminent toujours par un bit de valeur opposée au premier bit. Cette représentation permet de définir une représentation dite squelettique permettant de regrouper les séquences inverses sous un même squelette ; ainsi les deux séquences de période 7 ( 0000001 et 1111110 ) ont pour squelette la valeur 61 (6 = nombre de bits identiques commençant la séquence ; 1 : nombre de bits de parité inverse aux premiers). Un avantage de la représentation squelettique est de permettre la constitution d'une relation d'ordre strict permettant d'ordonner les séquences et de s'assurer de leur unicité. Elle permet également de construire de manière exhaustive tous les squelettes de séquences canoniques et d'en déduire toutes les séquences possibles en respectant les règles suivantes - un squelette de séquence canonique est un nombre comportant un nombre pair de chiffres - un squelette de séquence canonique n'est pas décomposable en séquences paires identiques (squelettes de séquences plus courtes) le premier chiffre est supérieur ou égal aux suivants la somme des chiffres du squelette est égale à la période de la séquence Ainsi les squelettes viables ordonnés sont les suivants : Période 3: 21 soit 2 séquences inverses bit à bit l'une de l'autre (on les notera 21 / 0 et 21 / 1) Période 5: 41, 32, 2111 soit 6 séquences inverses bit à bit deux à deux Période 6: 51, 42, 33, 3111, 2211 soit 9 séquences car le squelette 33 est symétrique et ne donne lieu qu'à une séquence unique (33 / 0 = 33 / 1). A noter que les squelettes 2121 et 111111 n'ont pas été retenus car le premier est en fait celui d'une séquence de période 3 (21) et le second celui de la séquence unique de période 2 (11) que l'on souhaite écarter. Période 7 : 61, 52, 43, 4111, 3211, 3121, 3112, 2221, 211111 soit 18 séquences On voit qu'avec seulement 3 bits d'états il est possible de coder 35 machines d'état différentes générant des séquences distinctes et 15 compatibles entre elles (conformément au jeu de règles cité plus haut) de période comprise entre 3 et 7 (en évitant les séquences de période puissance de 2). Pour opérer le choix des séquences optimales pour un système de 20 gestion de FIFO, on définit une distance d'auto-ambiguïté propre à un code séquentiel, DA''' , et une distance d'ambiguïté entre deux codes séquentiels i et j, DA'''. La distance d'auto-ambiguïté DA''' est la taille exprimée en nombre de bits de la plus longue sous-séquence de bits successifs appartenant à deux avatars quelconques de la séquence 25 considérée, le second étant obtenu par décalage du premier d'un nombre entier de bits. La distance d'ambiguïté entre deux séquences DA''' est la taille exprimée en nombre de bits de la plus longue sous-séquence de bits successifs appartenant à la fois aux deux séquences considérées. Le critère de choix préféré consiste à minimiser d'une part la distance d'auto- 30 ambiguïté et d'autre part les distances d'ambiguïté entre les séquences distinctes prises deux à deux pour deux FIFO adjacentes. Pour connaître les distances d'ambiguïté entre deux séquences (ou d'auto-ambiguïté d'une séquence), on constitue pour chaque élément une séquence double par juxtaposition de deux représentations identiques et on fait 10 glisser les deux trains de bits ainsi obtenus l'un par rapport à l'autre en détectant chaque fois la plus grande section de bits identiques. L'exemple suivant illustre la détermination des distances d'auto-ambiguïté 5 des séquences de longueur 5, indexées � i � Séquence 41 / 0 : 00001 0000100001 0001000010 3 => DA''' = 3 10 0000100001 0010000100 2 0000100001 0100001000 2 0000100001 15 1000010000 3 => DA''' = 3 II en est de même pour la séquence 41 / 1 : 11110 Séquence 32 / 0 : 00011 0001100011 20 0011000110 2 => DA''' = 2 0001100011 0110001100 1 0001100011 1100011000 1 25 0001100011 1000110001 2 => DA''' = 2 Il en est de même pour la séquence 32 / 1 : 11100 Séquence 2111 / 0 : 00101 30 0010100101 0101001010 1 0010100101 1010010100 3 => DA''' = 3 0010100101 35 0100101001 3 => DA''' = 3 0010100101 1001010010 1 II en est de même pour la séquence 2111 / 1 : 11010 L'exemple suivant illustre la détermination de la distance d'ambiguïté entre la séquence de longueur 7 43 / 0 indexée � i � et la séquence de longueur 5 32 / 1 indexée � j � : 43/0:00001 1 1 00001 1 1 32/1:11100111001110 2 11001110011100 7 => DA',i = 7 10011100111001 2 00111001110011 2 01110011100111 5 L'exemple suivant illustre la détermination de la distance d'ambiguïté entre la séquence de longueur 7 43 / 0 indexée � i � et la séquence de longueur 7 : 3121 / 1 indexée � j � : 43/0 :00001110000111 3121/1:11101101110110 3 11011011101101 1 10110111011011 2 0 1 1 0 1 1 1 0 1 1 0 1 1 1 4 => DAi'i = 4 11011101101110 2 10111011011101 1 01110110111011 3 Supposons que l'on souhaite protéger 4 FIFO adjacentes dans un espace mémoire contigu de 3K adresses, l'espace alloué à chaque FIFO étant configurable par blocs de 16 adresses successives. On souhaite avoir 4 séquences de période 7 de manière à minimiser la contrainte sur la taille de chaque FIFO. Les tailles interdites sont les multiples communs à 7 et 16 soit les multiples de 70 en hexadécimal : 70, E0, 150, 1CO, 230, 2A0, 310, 380, 3F0, 460, 4D0, 540, 5B0, 620, 690, 700, 770, 7E0, 850, 8CO3 930, 9A0, A10, A80, AFO, B60, BDO, soit 27 valeurs sur tout l'espace de 3K. Si on cherche à optimiser la détection des défaillances, on recherche - la distance d'auto-ambiguïté minimale pour les séquences utilisées, puis - la distance d'ambiguïté la plus faible possible pour les FIFO adjacentes. A titre d'illustration, le tableau de la figure 2 donne les valeurs des distances d'ambiguïté pour les 18 valeurs prises parmi les 27 ayant une distance d'auto-ambiguïté minimale. On voit que les séquences 3211/0, 3211/1, 3112/1, et 3112/0 optimisent la détection lorsqu'elles sont affectées respectivement aux FIFO 1, 2, 3 et 4. Dans ce cas, la distance io d'auto-ambiguïté est toujours 2, la distance d'ambiguïté des fifos adjacentes (1 et 2, 2 et 3, 3 et 4) est 3 ou 5 et la distance d'ambiguïté des FIFO non adjacentes (2 et 4) est 6. Ces exemples sont donnés à titre d'illustration de modes de réalisation de l'invention. Ils ne limitent en aucune manière le champ de l'invention qui 15 est défini par les revendications qui suivent. 20 REVENDICATIONS1. Dispositif de gestion des accès à un module de stockage de données comprenant au moins une mémoire (10) dont au moins un espace est géré de manière à produire une fonctionalité de type FIFO, ledit dispositif comprenant au moins une paire de pointeurs (20) des accès en écriture et en lecture à ladite mémoire et au moins un module (30) de génération d'au moins un code séquentiel dont une partie de séquence est écrite en même temps que chaque donnée, et de lecture et de vérification dudit code, caractérisé en ce que chaque code séquentiel généré est caractéristique de l'espace dans lequel la donnée est écrite. 2. Dispositif de gestion des accès à un module de stockage selon la revendication 1 caractérisé en ce que ledit code séquentiel est combiné avec une parité calculée sur la donnée. 3. Dispositif de gestion des accès à un module de stockage selon la revendication 1 caractérisé en ce que le code caractéristique de l'espace dans lequel la donnée est écrite est constitué par une séquence périodique de bits dont la période ne divise pas de façon entière le nombre de mots correspondant à la taille dudit espace. 4. Dispositif de gestion des accès à un module de stockage selon la revendication 1 caractérisé en ce que la distance d'auto-ambiguïté du code séquentiel est minimale. 5. Dispositif de gestion des accès à un module de stockage selon la revendication 1 caractérisé en ce que la somme des distances d'ambiguïté entre les codes séquentiels distincts appliqués à plusieurs mémoires adjacentes dudit module prises deux à deux est minimale. 6. Procédé de gestion des accès à un module de stockage de données comprenant au moins une mémoire dont au moins un espace est géré de manière à produire une fonctionalité de type FIFO, ledit procédécomprenant au moins une étape de pointage des accès en écriture et en lecture à ladite mémoire et au moins une étape de génération d'un code séquentiel, dont une partie de séquence est écrite en même temps que chaque donnée, et de lecture et de vérification dudit code, caractérisé en ce que chaque code généré est caractéristique de l'espace dans lequel la donnée est écrite. 7. Procédé de gestion des accès à un module de stockage selon la revendication 6 caractérisé en ce que la distance d'auto-ambiguïté du 1 o code séquentiel est minimale. 8. Procédé de gestion des accès à un module de stockage selon la revendication 6 caractérisé en ce que la somme des distances d'ambiguïté entre les codes séquentiels distincts appliqués à plusieurs 15 mémoires adjacentes dudit module prises deux à deux est minimale.