This repository was archived by the owner on Oct 30, 2023. It is now read-only.
Repository navigation
Expand file tree
/
Copy pathchapter_runtime.tex
More file actions
871 lines (753 loc) · 36.7 KB
/
Copy pathchapter_runtime.tex
File metadata and controls
871 lines (753 loc) · 36.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
\chapter[Vérification liée au modèle mémoire]{Vérification à l'exécution des annotations liées au modèle mémoire}
\label{sec:runtime}
\chapterintro
Dans ce chapitre nous abordons la vérification dynamique des annotations liées
au modèle mémoire.
Ceci requiert de pouvoir simuler un modèle mémoire bas niveau afin de pouvoir
surveiller les opérations bas niveau des programmes C (allocations,
initialisations, etc.).
En revanche, le modèle mémoire utilisé par le générateur de tests structurels
que nous utilisons n'est pas assez bas niveau et ne permet donc pas l'exécution
symbolique de ces constructions.
En conséquence, nous changeons d'approche pour ces propriétés.
En effet, contrairement au chapitre~\ref{sec:traduction}, ces annotations ne
seront pas vérifiées par test structurel mais par validation à l'exécution
({\em runtime assertion checking}).
Dans un premier temps nous présentons les différentes annotations que nous ne
pouvons pas traiter par génération de tests et que nous qualifions d'opérations
de bas niveau (partie~\ref{sec:mem-annots}).
Puis nous présentons quelques détails de conception de notre modèle mémoire
(partie~\ref{sec:mem-model}).
Enfin nous abordons les principes de l'instrumentation nécessaire pour la
vérification de ces annotations (partie~\ref{sec:mem-instru}).
\section{Annotations liées au modèle mémoire}
\label{sec:mem-annots}
Définissons d'abord quelques notions.
Les objets de la mémoire sont des blocs.
Chaque bloc est caractérisé par une adresse de base, une taille (en nombre
d'octets) et un contenu (qui peut être initialisé ou non).
Tout ceci constitue le modèle mémoire.
Les annotations \eacsl que nous considérons sont décrites dans la
figure~\ref{fig:gram-ext}.
Cette figure est une extension de la grammaire des termes et des prédicats
\eacsl définie au chapitre~\ref{sec:lang}.
\begin{figure}
\centering
\begin{tabular}{cc}
\begin{tabular}{lrl}
\textit{term} ::= & ... \\
& $\mid$
& \underline{\lstinline'\\base_addr'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
& $\mid$
& \underline{\lstinline'\\block_length'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
& $\mid$
& \underline{\lstinline'\\offset'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
\end{tabular}
&
\begin{tabular}{lrl}
\textit{pred} ::= & ... \\
& $\mid$
& \underline{\lstinline'\\valid'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
& $\mid$
& \underline{\lstinline'\\valid_read'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
& $\mid$
& \underline{\lstinline'\\initialized'} \underline{\lstinline'('} \textit{term} \underline{\lstinline')'} \\
\end{tabular}
\end{tabular}
\caption{Extension de la grammaire des termes et des prédicats
\label{fig:gram-ext}}
\end{figure}
\begin{figure}[bt]
\input{figures/fig_mem_annots}
\caption{Adresse de base, longueur du bloc et offset dans un bloc}
\label{fig:mem-annots}
\end{figure}
La figure~\ref{fig:mem-annots} illustre les annotations \lstinline{\base_addr},
\lstinline{\block_length} et \lstinline{\offset}.
On y voit un modèle mémoire simplifié contenant 3 blocs.
Le deuxième bloc est constitué de trois cases dénotées \lstinline't[0]',
\lstinline't[1]' et \lstinline't[2]', pouvant contenir chacune un entier.
Le pointeur \lstinline'p' pointe vers la deuxième case du deuxième bloc.
L'adresse de base de \lstinline'p' (\lstinline'\base_addr(p)') désigne le
début du bloc.
La longueur du bloc de \lstinline'p' (\lstinline'\block_length(p)') est la
taille du bloc à partir de son adresse de base (trois fois la taille d'un entier
sur cet exemple).
L'offset de \lstinline'p' (\lstinline'\offset(p)') est le décalage de
\lstinline'p' par rapport à son adresse de base (la taille d'un entier sur cet
exemple).
Donnons la sémantique informelle de chacune de ces annotations.
\baseaddrt retourne l'adresse de base du bloc alloué dans lequel pointe le
pointeur $t$.
\blocklengtht retourne la longueur (en octets) du bloc alloué dans lequel
pointe le pointeur $t$.
\offsett retourne le décalage (en octets) entre $t$ et l'adresse de
base du bloc dans lequel pointe $t$.
\validt, respectivement \validreadt, est vrai si le déréférencement de
$t$ est autorisé en lecture et en écriture, respectivement au moins en
lecture.
\validt implique \validreadt mais l'inverse n'est pas vrai.
\initializedt est un prédicat prenant en paramètre un pointeur $t$ sur une
left-value $lv$, il est vrai si $lv$ est initialisée.
Soit une mémoire $\mem = (\env, \store)$ en accord avec la formalisation des
mémoires du chapitre~\ref{sec:lang}.
\initializedt est vrai s'il existe une left-value $lv$ et une adresse $\loc$
telles que $\env(lv) = \loc$, le pointeur $t$ a pour valeur $\loc$ et
$\store(\loc) \neq \bot$.
\lstinputlisting[caption={Annotations mémoire -- Exemple en C},
label=lst:mem-annots,firstline=4,firstnumber=1]{listings/mem_annots.c}
\begin{figure}[h!]
\lstinputlisting[caption={Version instrumentée du programme du listing~\ref{lst:mem-annots}},
label=lst:mem-annots-instru]{listings/mem_annots_instru.c}
\end{figure}
Le listing~\ref{lst:mem-annots} illustre l'utilisation de toutes ces annotations
sur un programme C.
Un tableau \lstinline't' de trois entiers est alloué ligné 2.
Les deux premières cases du tableau sont initialisées à 1 aux lignes 3--4.
Un pointeur \lstinline'p' est ensuite initialisé à \lstinline't+1' ligne 5,
c'est-à-dire pointe la deuxième case du tableau.
L'assertion ligne 6 affirme que \lstinline'p' et \lstinline't' ont la même
adresse de base.
L'assertion ligne 7 affirme que le bloc contenant \lstinline'p' a une taille de
trois entiers.
L'assertion ligne 8 affirme que \lstinline'p' a un offset de la taille d'un
entier dans son bloc.
L'assertion ligne 9 affirme que \lstinline'p' peut être déréférencé sur les
offsets 0 et 1 (\lstinline'*(p+0)' et \lstinline'*(p+1)').
L'assertion ligne 10 affirme que \lstinline'*p' est initialisé mais pas
\lstinline'*(p+1)'.
Les annotations du programme sont satisfaites : leur vérification à l'exécution
ne produit pas d'erreur.
Le listing~\ref{lst:mem-annots-instru} présente le programme du
listing~\ref{lst:mem-annots} instrumenté afin de vérifier les annotations à
l'exécution.
Les lignes 15--17 du listing~\ref{lst:mem-annots-instru} permettent d'exécuter
l'assertion ligne 6 du listing~\ref{lst:mem-annots}.
Les lignes 19--22 du listing~\ref{lst:mem-annots-instru} permettent d'exécuter
l'assertion ligne 7 du listing~\ref{lst:mem-annots}.
Les lignes 24--26 du listing~\ref{lst:mem-annots-instru} permettent d'exécuter
l'assertion ligne 8 du listing~\ref{lst:mem-annots}.
Les lignes 28--37 du listing~\ref{lst:mem-annots-instru} permettent d'exécuter
l'assertion ligne 9 du listing~\ref{lst:mem-annots}.
Les lignes 39--48 du listing~\ref{lst:mem-annots-instru} permettent d'exécuter
l'assertion ligne 10 du listing~\ref{lst:mem-annots}.
Les appels de la fonction \lstinline'__store_block' (lignes 4--5) servent à
enregistrer les blocs des nouvelles variables.
Les appels de la fonction \lstinline'__delete_block' (lignes 50--51) permettent
de les désinscrire à la fin de leur existence.
\section{Modèle mémoire pour la vérification à l'exécution}
\label{sec:mem-model}
Dans cette partie, nous présentons les détails de conception du modèle mémoire
proposé.
Nous justifions nos choix d'implémentation puis présentons les algorithmes de
calcul du plus grand préfixe commun, de recherche, d'ajout et de suppression
d'un bloc dans le modèle mémoire.
\subsection{Structure de données ``store''}
Au chapitre~\ref{sec:lang}, nous avons défini un {\em store} comme étant une
fonction associant une valeur à une adresse.
Dans ce chapitre, ce terme fait référence à une structure de données qui
implémente efficacement cette fonction, donc contenant des adresses et des
valeurs associées.
C'est dans le {\em store} que les informations sur la validité et
l'initialisation des blocs mémoire seront enregistrées et recherchées par la
suite.
Le code instrumenté pouvant accéder et modifier fréquemment les données du
{\em store}, une implémentation efficace requiert une structure de données
offrant une bonne complexité en temps et en espace.
Cette structure de données doit être triée : on peut avoir besoin d'accéder
directement à un bloc à partir de son adresse de base, mais aussi à partir de
n'importe quelle adresse contenue dans le bloc (c'est-à-dire entre l'adresse de
base et l'adresse de fin du bloc).
Par exemple, la fonction \lstinline'__base_addr' utilisée pour le traitement
de la construction \baseaddrt cherche l'adresse de base la plus proche et
inférieure à $t$.
Cette contrainte ne nous permet pas d'utiliser une table de hachage.
Les listes chaînées ne sont pas assez efficaces à cause de la complexité
linéaire dans le pire cas.
Les arbres binaires de recherche non équilibrés ont aussi une complexité
linéaire dans le pire des cas quand les données sont insérées dans un ordre
strictement croissant ou strictement décroissant.
Certes, le coût du rééquilibrage de l'arbre (pour un arbre binaire de recherche
équilibré) serait amorti dans le cas où les modifications de la structure de
l'arbre sont moins nombreuses que les accès simples; mais ce n'est pas
nécessairement vrai sur les exemples de code que nous avons instrumentés comme
nous le verrons au chapitre~\ref{sec:eacsl}.
Notre choix s'est donc porté sur la structure de {\em Patricia trie}
\cite{Szpankowski/90} (appelé aussi {\em radix tree} ou ``arbre à préfixe
compact'').
Cette structure est efficace même si l'arbre n'est pas équilibré.
Les clés sont les adresses de base des blocs (c'est-à-dire des mots de 32 ou 64
bits) ou des préfixes d'adresses.
Chaque feuille contient les données relatives à un bloc en mémoire (voir
partie~\ref{sec:mem-annots} pour le détail des informations stockées).
Le routage de la racine jusqu'à une feuille particulière se fait grâce aux
n\oe{}uds internes.
Chacun d'eux contient le plus grand préfixe de l'adresse de base commun entre
ses deux fils.
La figure~\ref{fig:insertion-Patricia-trie-0} illustre un Patricia
trie sur des adresses 8 bits, limite choisie pour des raisons de simplicité.
Il contient trois blocs représentés par trois feuilles.
Seules les adresses de base apparaissent sur le schéma.
Il contient deux préfixes stockés dans les n\oe{}uds qui ne sont pas des
feuilles.
Le symbole ``{\tt *}'' signifie que la valeur du bit à cette position n'a pas
d'importance.
\begin{figure}[h]
\input{figures/fig_add_patricia_trie}
\label{fig:insertion-Patricia-trie-0}
\end{figure}
La complexité théorique dans le pire des cas d'un accès dans un Patricia trie
dans notre cas est en $O(k)$ où $k$ est la longueur d'un mot (c'est-à-dire
32 ou 64 bits).
En pratique, un programme ne pouvant allouer des blocs que dans un
espace mémoire limité, la profondeur de l'arbre est inférieure à cette borne.
De plus, contrairement aux chaînes de caractères (la première application des
Patricia tries), la comparaison des mots de bits peut être implémentée très
efficacement par des opérations bit-à-bit.
Les données de chaque bloc n'occupent que quelques octets en mémoire, exception
faite des données d'initialisation du bloc.
Le statut d'initialisation de chaque octet est monitoré séparément
(lignes 8 et 10 du listing~\ref{lst:mem-annots-instru}) et les champs
de bits ne sont pas supportés.
Dans le pire cas (bloc partiellement initialisé), chaque octet utilise un bit
supplémentaire portant l'information sur son initialisation.
Nous conservons le nombre d'octets initialisés de chaque bloc dans un
compteur.
Dans le cas où tous les octets (ou aucun) sont initialisés, le tableau censé
contenir les bits portant l'information d'initialisation est libéré et nous
utilisons alors la valeur du compteur pour avoir cette information.
De plus, nous utilisons une fonction spécifique (ligne 12 du
listing~\ref{lst:mem-annots-instru}) dans le cas où tous les octets
d'un bloc sont initialisés d'un coup, au lieu d'invoquer une fonction
d'initialisation sur chaque octet du bloc.
\subsection{Calcul du masque du plus grand préfixe commun (MPGPC)}
\label{sec:mpgpc}
Définissons les types {\em word} et {\em Mask} utilisés dans ce chapitre.
Un {\em word} de taille $n$ est une suite de $n$ bits ($0$ ou $1$).
La taille d'un word est généralement un multiple de $2$ et dépend de
l'architecture matérielle.
Nous utiliserons la constante \lstinline'NULL' pour dénoter l'adresse
nulle et nous noterons $word$ le type des words.
Nous utilisons une constante $WLEN$ pour faire référence à la taille des words.
Un {\em masque} est un word dont les $k \le WLEN$ premiers bits sont à $1$ et
les $WLEN-k$ bits suivants sont à $0$.
Nous noterons $Mask$ le type des masques.
Les types de données {\em word} et {\em Mask} seront utilisés dans les
algorithmes présentés dans ce chapitre.
Nous définissons un ordre lexicographique sur les masques.
Soient $m$ et $m'$ deux masques, $m \le m'$ si et seulement si $m'$ contient au
moins autant de $1$ que $m$.
Le {\em masque du plus grand préfixe commun} $m$ de deux adresses $a$ et $b$ est
le plus grand des masques (suivant l'ordre lexicographique) tel que, si $n$ est
le nombre de $1$ de $m$, alors les $n$ premiers bits de $a$ et $b$ sont
identiques.
On dira aussi que $n$ est la taille du préfixe commun à $a$ et $b$.
Par exemple, le masque du plus grand préfixe commun de $a$ =
\ppleaf{\texttt{0110\,0111}} et $b$ = \ppleaf{\texttt{0111\,1111}} est
$m$ = \texttt{1110\,0000}.
En effet, seuls les trois premiers bits de $a$ sont identiques au trois premiers
bits de $b$, les words divergent à partir du quatrième bit.
On notera $p$ = \ppnode{\texttt{011*\,****}} le plus grand préfixe commun à $a$
et $b$, où le symbole ``{\tt *}'' signifie que la valeur du bit à cette position
ne fait pas partie du préfixe commun.
\begin{algorithm}
\begin{algorithmic}[1]
\Statex $array[ 0 .. \mathit{WLEN} ]$ of Mask $\mathit{masks}$
\Comment{masques dans l'ordre lexicographique}
\Statex $array[ 0 .. \mathit{WLEN} ]$ of int $\mathit{longer}$
\Comment{indices des masques plus longs à tester}
\Statex $array[ 0 .. \mathit{WLEN} ]$ of int $\mathit{shorter}$
\Comment{indices des masques plus courts à tester}
\Statex
\Ensure $(a \Band \mresult) == (b \Band \mresult)$
\Ensure $\forall i. (0 \le i \le \mathit{WLEN} \Rightarrow (\mathit{masks}[i] \Band a) == (\mathit{masks}[i] \Band b) \Rightarrow \mresult \ge \mathit{masks}[i])$
\Ensure $\exists i. (0 \le i \le \mathit{WLEN} \land \mresult == \mathit{masks}[i])$
\Statex
\Function{MPGPC}{word $a$, $b$}
\State int $i$, word $nxor$
\Let{$\mathit{nxor}$}{$~\sim(a ~\string^{}~ b)$}
\Comment{$\string^{}$ : ``ou'' exclusif bit-à-bit, $\sim$ : ``non'' bit-à-bit}
\State $i \gets \mathit{WLEN}/2$
\While{$i > 0$}
\If{$\mathit{nxor} \ge \mathit{masks}[i]$}
\State $i \gets \mathit{longer}[i]$
\Else
\State $i \gets \mathit{shorter}[i]$
\EndIf
\EndWhile\\
\Return $masks[-i]$
\EndFunction
\end{algorithmic}
\caption{Recherche du masque du plus grand préfixe commun de $a$ et $b$
\label{algo:prefix}}
\end{algorithm}
\begin{definition}[Masque du plus grand préfixe commun (MPGPC)]
Le MPGPC de $a$ et $b$ est le plus grand masque inférieur ou égal à la
négation du ou exclusif de $a$ et de $b$.
\end{definition}
Nous présentons maintenant un algorithme efficace de recherche du masque du plus
grand préfixe commun de deux adresses.
Une version na\"ive et inefficace de cet algorithme consiste en un parcours
linéaire des mots mémoire de gauche à droite jusqu'à trouver des bits
différents, de la même manière qu'on pourrait le faire sur des chaînes de
caractères.
La complexité de la version na\"ive est en $\mathcal{O}(\mathit{WLEN})$.
La version optimisée de cet algorithme consiste en une recherche
dichotomique du masque dans un tableau pré-calculé qui contient tous les masques
de préfixes possibles.
L'algorithme~\ref{algo:prefix} présente cette méthode de recherche.
La complexité de cet algorithme est en
$\mathcal{O}(\mathit{log}(\mathit{WLEN}))$ (soit $\le 6$ itérations pour des
words de 32 bits et $\le 7$ itérations pour des words de 64 bits).
Les transitions entre les étapes de la recherche se font en utilisant des
indices pré-calculés, de manière à obtenir le prochain masque à comparer avec
$nxor$.
La variable $nxor$ contient la négation du ou exclusif de $a$ et $b$.
Le tableau $masks$ contient tous les $WLEN+1$ masques possibles sur
$WLEN$ bits.
Les tableaux $longer$ et $shorter$ contiennent des indices du tableau $masks$.
Si $nxor$ est plus grand que le masque courant à l'indice $i$ ($masks[i]$), le
prochain masque à comparer avec $nxor$ sera celui à l'indice $longer[i]$
($masks[longer[i]]$).
Si $nxor$ est plus petit que le masque courant, le prochain masque à comparer
avec $nxor$ sera à l'indice $shorter[i]$.
Si l'indice courant $k$ est négatif, alors $- k$ est l'indice du masque
du plus grand préfixe commun.
Sur des words de longueur 8 bits, les tableaux $masks$, $longer$ et $shorter$
sont initialisés de cette manière :
\begin{lstlisting}
// index 0 1 2 3 4 5 6 7 8
byte masks[] = {0x00,0x80,0xC0,0xE0,0xF0,0xF8,0xFC,0xFE,0xFF};
int longer [] = { 0, -1, 3, -3, 6, -5, 7, 8, -8};
int shorter[] = { 0, 0, 1, -2, 2, -4, 5, -6, -7};
\end{lstlisting}
Considérons deux words de 8 bits $a$ = \ppleaf{\texttt{0110\,0111}} et
$b$ = \ppleaf{\texttt{0111\,1111}}.
$nxor$ prend la valeur \texttt{1110\,0111}.
L'algorithme essaie $i = 4$ d'abord, puis $i = shorter[4] = 2$, puis
$i = longer[2] = 3$, puis $i = longer[3] = -3$, pour finalement retourner
$masks[3] = 0xE0$, qui est \texttt{1110\,0000}, soit précisément le masque du
plus grand préfixe commun de $a$ et $b$.
\subsection{Recherche}
Présentons maintenant les algorithmes de recherche d'un bloc dans le
\textit{store} à partir d'une adresse $a$.
Ils sont de deux sortes.
La recherche exacte cherche un bloc dont l'adresse de base est égale à $a$, elle
est notamment utilisée dans l'instrumentation des fonctions \lstinline'free' et
\lstinline'realloc'.
La recherche du contenant cherche un bloc qui contient $a$, c'est-à-dire que
$a$ est incluse entre le début (adresse de base) et la fin du bloc.
Elle est notamment utilisée dans l'instrumentation des annotations
\lstinline'\valid' et \lstinline'\base_addr'.
Dans ces algorithmes, nous noterons $Ptree$ le type de données des Patricia
tries et $Block$ le type des blocs.
Voici une définition simplifiée de ces types :
\begin{lstlisting}
Block = { word ptr; int size; };
Ptree = {
bool isLeaf;
word addr;
Mask mask;
Ptree left, right, father;
Block leaf;
};
\end{lstlisting}
Un objet de type $Block$ est caractérisé par un word et une taille.
Un objet de type $Ptree$ est quant à lui caractérisé par un booléen indiquant
si l'arbre est une feuille, un word encodant la valeur et le masque
du plus grand préfixe commun à ses deux fils, le sous-arbre gauche, le
sous-arbre droit, le n\oe{}ud ``père'' et le bloc porté par le n\oe{}ud si c'est
une feuille.
Par exemple pour la racine du Patricia trie de la
figure~\ref{fig:insertion-Patricia-trie-0} \textbf{(a)}, les deux champs
\lstinline'addr = 0010 0000' et \lstinline'mask = 1111 0000' encodent le
préfixe \ppnode{\texttt{0010\,****}}.
Nous utiliserons la constante $emptyPtree$ pour dénoter un Patricia trie vide.
\subsubsection*{Recherche exacte}
\begin{algorithm}
\begin{algorithmic}[1]
\Require $root \neq emptyPtree \land a \neq \mnull$
\Ensure $\mresult \neq noBlock \Rightarrow \mresult.ptr == a$
\Statex
\Function{Find-exact}{Ptree $root$, word $a$}
\State Ptree $x$
\Let{$x$}{$root$}
\While{$\lnot \mathit{x.isLeaf}$}
\If{$(\mathit{x.addr} \Band \mathit{x.mask}) \neq (a \Band \mathit{x.mask})$}
\Return $noBlock$
\EndIf
\If{$(\mathit{x.right.addr} \Band \mathit{x.right.mask}) == (a \Band \mathit{x.right.mask})$}
\State $x \gets \mathit{x.right}$
\ElsIf{$(\mathit{x.left.addr} \Band \mathit{x.left.mask}) == (a \Band \mathit{x.left.mask})$}
\State $x \gets \mathit{x.left}$
\Else{} \Return $noBlock$
\EndIf
\EndWhile
\If{$a \neq \mathit{x.leaf.ptr}$}
\Return $noBlock$
\Else{}
\Return $\mathit{x.leaf}$
\EndIf
\EndFunction
\end{algorithmic}
\caption{Recherche du bloc d'adresse de base $a$, dans Block $\cup$ \{noBlock\}
\label{algo:get-exact}}
\end{algorithm}
L'algorithme~\ref{algo:get-exact} retourne le bloc $B$ dont l'adresse de base
est égale à l'adresse $a$ passée en paramètre si un tel bloc est dans le store,
ou la valeur $noBlock$ sinon.
Nous notons $root$ le {\em store} global représenté par un Patricia trie, dans
lequel tous les blocs sont enregistrés.
L'algorithme procède comme suit : tant que $x$ n'est pas une feuille -- c'est
donc un n\oe{}ud interne ayant deux fils -- on se dirige vers le fils ayant le
plus grand préfixe commun avec l'adresse $a$ passée en paramètre de
l'algorithme.
Quand on arrive sur une feuille, cette dernière contient l'adresse que l'on
cherchait.
\subsubsection*{Recherche du ``contenant''}
\begin{algorithm}[h!]
\begin{algorithmic}[1]
\Function{Find-cont}{Ptree $root$, word $a$}
\Statex Ptree $x$, Stack $stack$
\If{$(\mathit{root} == emptyPtree) \lor (a == \mnull)$}
\Return $noBlock$
\Else
\Let{$x$}{$root$}
\Let{$stack$}{$\mathit{emptyStack}$}
\While{$\mathit{true}$}
\If{$x.isLeaf$}
\If{$\mathit{x.addr} > a$}
\If{$stack = \mathit{emptyStack}$}
\Return $noBlock$
\Else
\State $x \gets \mathit{pop(stack)}$
\State $\mathit{continue}$
\EndIf
\ElsIf{$a < \mathit{x.leaf.size} + \mathit{x.addr}$}
\Return $\mathit{x.leaf}$
\ElsIf{$\mathit{x.leaf.size} == 0 \land a == \mathit{x.leaf.ptr}$}
\Return $\mathit{x.leaf}$
\ElsIf{$\mathit{stack} = \mathit{emptyStack}$}
\Return $noBlock$
\Else
\State $x \gets \mathit{pop(stack)}$
\State $\mathit{continue}$
\EndIf
\EndIf
\If{$\mathit{x.right.addr} \Band \mathit{x.right.mask} \le a \Band \mathit{x.right.mask}$}
\State $\mathit{stack} \gets \mathit{push(x.left)}$
\State $x \gets \mathit{x.right}$
\ElsIf{$\mathit{x.left.addr} \Band \mathit{x.left.mask} \le a \Band \mathit{x.left.mask}$}
\State $x \gets \mathit{x.left}$
\ElsIf{$\mathit{stack} == \mathit{emptyStack}$}
\Return $noBlock$
\Else
\State $x \gets \mathit{pop(stack)}$
\EndIf
\EndWhile
\EndIf
\EndFunction
\end{algorithmic}
\caption{Recherche du bloc contenant une adresse $a$, dans Block $\cup$
\{noBlock\}
\label{algo:get-cont}}
\end{algorithm}
L'algorithme~\ref{algo:get-cont} retourne le bloc $B$ contenant
l'adresse $a$ passée en paramètre, c'est-à-dire que l'adresse $a$ est plus
grande que l'adresse de base de $B$ et plus petite que l'adresse de fin de $B$
(adresse de base du bloc + taille du bloc).
Si un tel bloc n'existe pas, la valeur $noBlock$ est renvoyée.
Cet algorithme est utilisé pour des requêtes du type \lstinline{\valid} ou
\lstinline{\initialized} où l'adresse passée en paramètre ne correspond pas
nécessairement à l'adresse de base d'un bloc.
Cet algorithme est similaire à celui de la recherche exacte, au détail près
qu'il faut vérifier que $a$ est comprise entre l'adresse de base et l'adresse
de fin de $B$ quand on arrive sur une feuille.
On utilise une pile $stack$ contenant les n\oe{}uds à partir desquels il faut
reprendre le parcours si la recherche n'aboutit pas.
Nous notons $Stack$ le type de la pile, $emptyStack$ une pile vide, $push$ la
fonction d'empilement et $pop$ la fonction de dépilement.
Quand on explore le fils droit, on empile le fils gauche.
Quand on arrive sur une feuille, on vérifie que $a$ est comprise entre l'adresse
de base et l'adresse de fin du bloc.
Si c'est le cas alors on a trouvé le bloc que l'on cherchait.
Sinon on utilise le dernier n\oe{}ud empilé (et on le dépile) s'il existe,
sinon on retourne $noBlock$.
L'instruction $continue$ aux lignes 12 et 18 de l'algorithme~\ref{algo:get-cont}
indique que l'exécution ignore les instructions suivantes et reprend au début de
la boucle à la ligne 6.
\subsection{Ajout d'un bloc}
La figure~\ref{fig:insertion-Patricia-trie} illustre l'insertion de l'adresse
\ppleaf{\texttt{0010\,0111}} dans un arbre.
L'algorithme~\ref{algo:add-block} a déterminé que le n\oe{}ud le plus similaire
est \ppleaf{\texttt{0010\,0110}}, et crée le père correspondant :
\ppnode{\texttt{0010\,011*}}.
\begin{figure}[h]
\input{figures/fig_add_patricia_trie}
\label{fig:insertion-Patricia-trie}
\end{figure}
\begin{algorithm}[tb]
\begin{algorithmic}[1]
\Procedure{Add}{Ptree $root$, Block $a$}
\Statex Ptree $x$, $b$, $f$; Mask $lprefix$, $rprefix$
\State $x.addr \gets a.ptr$, $x.mask \gets masks[WLEN]$, $x.left \gets emptyPtree$,
\State $x.right \gets emptyPtree$, $x.father \gets emptyPtree$, $x.leaf \gets a$
\If{$root == emptyPtree$}
\Let{$root$}{$x$}
\Else
\Let{$b$}{$root$}
\While{$\mathit{true}$}
\If{$b.isLeaf$}
\State $\mathit{break}$
\EndIf
\Let{$lprefix$}{$MPGPC(\mathit{b.left.addr} \Band \mathit{b.left.mask},\mathit{a.ptr})$}
\Let{$rprefix$}{$MPGPC(\mathit{b.right.addr} \Band \mathit{b.right.mask},\mathit{a.ptr})$}
\If{$lprefix > rprefix$}
\Let{$b$}{$b.left$}
\ElsIf{$rprefix > lprefix$}
\Let{$b$}{$b.right$}
\Else
\State $\mathit{break}$
\EndIf
\EndWhile
\Let{$f.addr$}{$b.addr \Band x.addr$}
\Let{$f.leaf$}{$noBlock$}
\Let{$f.left$}{$(\mathit{x.addr} \le \mathit{b.addr})~?~x~:~b$}
\Let{$f.right$}{$(\mathit{x.addr} \le \mathit{b.addr})~?~b~:~x$}
\Let{$x.father$}{$f$}
\If{$b == root$}
\Let{$f.father$}{$emptyPtree$}
\Let{$f.mask$}{$MPGPC(b.addr \Band b.mask, a.ptr)$}
\Let{$root$}{$f$}
\Else
\If{$b.father.left == b$}
\Let{$b.father.left$}{$f$}
\Else
\Let{$b.father.right$}{$f$}
\EndIf
\Let{$f.father$}{$b.father$}
\Let{$f.mask$}{$MPGPC(f.left.addr \Band f.left.mask, f.right.addr \Band f.right.mask)$}
\EndIf
\Let{$b.father$}{$f$}
\If{$\lnot b.isLeaf$}
\Let{$b.mask$}{$MPGPC(b.left.addr \Band b.left.mask, b.right.addr \Band b.right.mask)$}
\EndIf
\EndIf
\EndProcedure
\end{algorithmic}
\caption{Ajout d'un bloc $a$, modifie le Ptree $root$
\label{algo:add-block}}
\end{algorithm}
L'algorithme~\ref{algo:add-block} présente l'ajout d'un nouvel élément $a$ à
l'arbre du {\em store}.
Si l'arbre est vide, l'élément est ajouté à la racine.
Sinon, on recherche le n\oe{}ud $b$ (qui n'est pas nécessairement une feuille)
le plus similaire au n\oe{}ud à insérer.
Celui-ci sera son frère dans la nouvelle configuration de l'arbre.
Nous créons ensuite le n\oe{}ud correspondant au père.
Le plus grand préfixe commun des deux fils est calculé pour le père, et les fils
sont ordonnés en fonction de leur adresse (le plus petit à gauche).
Puis le père est inséré dans l'arbre à l'ancien emplacement de $b$.
Les champs de $b$ et de l'ancien père de $b$ (s'il existe) sont également mis à
jour pour maintenir la cohérence de l'arbre.
\subsection{Suppression d'un bloc}
La figure~\ref{fig:suppression-Patricia-trie} illustre la suppression de
l'adresse \ppleaf{\texttt{0010\,0111}} dans un Patricia trie.
Ce n\oe{}ud ainsi que son père \ppnode{\texttt{0010\,011*}} sont supprimés, et
\ppleaf{\texttt{0010\,0110}} est remonté d'un niveau.
\input{figures/fig_rem_patricia_trie}
\begin{algorithm}[tb]
\begin{algorithmic}[1]
\Require $root \neq emptyPtree \land B \neq noBlock$
\Statex
\Procedure{Rem}{Ptree $root$, Block $B$}
\Statex Ptree $x$, $b$, $f$, $g$
\Let{$x$}{$root$}
\While{$\lnot x.isLeaf$}
\If{$\mathit{x.right.addr} \Band \mathit{x.right.mask} == \mathit{B.ptr} \Band \mathit{x.right.mask}$}
\Let{$x$}{$x.right$}
\Else
\Let{$x$}{$x.left$}
\EndIf
\EndWhile
\Let{$f$}{$x.father$}
\If{$f == emptyPtree$}
\Let{$root$}{$emptyPtree$}
\Else
\Let{$b$}{$(x == \mathit{f.left}) ~?~ \mathit{f.right} ~:~ \mathit{f.left}$}
\Let{$f$}{$b$}
\If{$\lnot b.isLeaf$}
\Let{$b.left.father$}{$f$}
\Let{$b.right.father$}{$f$}
\EndIf
\Let{$g$}{$f.father$}
\If{$g \neq emptyPtree$}
\Let{$g.mask$}{$MPGPC(\mathit{g.left.addr} \Band \mathit{g.left.mask}, \mathit{g.right.addr} \Band \mathit{g.right.mask})$}
\EndIf
\EndIf
\EndProcedure
\end{algorithmic}
\caption{Suppression d'un bloc $B$, modifie le Ptree $root$
\label{algo:rem-block}}
\end{algorithm}
La procédure de suppression d'un bloc $B$ porté par une feuille du Patricia trie
est présentée par l'algorithme~\ref{algo:rem-block}.
L'algorithme commence par rechercher la feuille $x$ qui porte le bloc $B$.
Si cet élément est la racine, l'arbre devient vide.
Sinon, Cette feuille a un frère $b$ et un père $f$.
$B$ et son père $f$ sont supprimés, et $b$ remonte d'un niveau (et prend donc
la place de $f$).
Enfin, les champs du nouveau père de $b$ ($g$) sont mis à jour pour
maintenir la cohérence de l'arbre (le masque du plus grand préfixe commun est
recalculé).
\section{Instrumentation pour la vérification à l'exécution}
\label{sec:mem-instru}
Nous présentons l'instrumentation d'un programme C annoté dans une optique de
vérification à l'exécution des annotations liées au modèle mémoire.
Certaines instructions C doivent être instrumentées afin d'enregistrer à
l'exécution des informations sur la mémoire, et les annotations sont
instrumentées afin de pouvoir utiliser ces informations.
\subsection{Instrumentation des allocations et affectations}
Dans cette partie, nous définissons de manière informelle l'instrumentation à
opérer sur le programme annoté afin de pouvoir observer les allocations et
les affectations en mémoire.
Comme nous l'avons vu, pour traiter ces annotations \eacsl, nous devons
conserver pour chaque bloc les informations suivantes : l'adresse de base, le
nombre d'octets occupés en mémoire, l'initialisation de chaque octet et un
booléen indiquant si le bloc est en lecture seule (par exemple si c'est une
chaîne littérale).
Afin d'enregistrer ces informations nous définissons les fonctions C suivantes.
La fonction \lstinline'__store_block', qui prend en paramètre un pointeur et une
taille en octets, ajoute un bloc dans le \textit{store} (présenté en
partie~\ref{sec:mem-model}).
La fonction \lstinline'__store_block' est invoquée sur chaque variable locale
et paramètre formel de fonction (au début de leur portée), ainsi que sur chaque
variable globale (au début de la fonction \lstinline'main').
Elle utilise l'algorithme~\ref{algo:add-block}.
La fonction \lstinline'__delete_block' permet d'enlever du \textit{store} un
bloc reçu en paramètre.
Elle est appelée en fin de portée d'une variable et utilise
l'algorithme~\ref{algo:rem-block}.
Nous définissons également des ``surcouches'' aux fonctions de la bibliothèque
standard du C : \lstinline'malloc', \lstinline'realloc', \lstinline'calloc' et
\lstinline'free'.
L'instrumentation va substituer les appels à ces fonctions par un appel à nos
fonctions : \lstinline'__malloc', \lstinline'__realloc', \lstinline'__calloc'
et \lstinline'__free'.
Ces fonctions permettent d'ajouter ou de supprimer automatiquement les blocs
au \textit{store}, ainsi que de transférer les informations d'initialisation
d'un bloc à un autre en cas d'application de la fonction \lstinline'realloc'.
Enfin, nous définissons une fonction \lstinline'__initialize' qui permet de
marquer un certain nombre d'octets d'un bloc comme étant initialisés.
L'instrumentation ajoute des appels à cette fonction pour chaque affectation du
programme original, ainsi que pour chaque variable globale (initialisée à 0 par
défaut en C).
\subsection{Instrumentation des annotations}
\begin{figure*}[b!]
\scriptsize{
{\myinference{$\tau$-base-addr}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\base_addr('}t\mbox{\lstinline')'}) \trule
(I \concat
(l, \mbox{\lstinline'void* var_'}n~
\mbox{\lstinline'= __base_addr('}e\mbox{\lstinline');'}),
\mbox{\lstinline'var_'}n)
}{}
}
{\myinference{$\tau$-block-length}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\block_length('}t\mbox{\lstinline')'}) \trule
(I \concat
(l, \mbox{\lstinline'unsigned long var_'}n~
\mbox{\lstinline'= __block_length('}e\mbox{\lstinline');'}),
\mbox{\lstinline'var_'}n)
}{}
}
{\myinference{$\tau$-offset}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\offset('}t\mbox{\lstinline')'}) \trule
(I \concat
(l, \mbox{\lstinline'int var_'}n~
\mbox{\lstinline'= __offset('}e\mbox{\lstinline');'}),
\mbox{\lstinline'var_'}n)
}{}
}
{\myinference{$\pi$-valid}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\valid('}t\mbox{\lstinline')'}) \prule
(I \concat
(l, \mbox{\lstinline'int var_'}n~
\mbox{\lstinline'= __valid('}e,\mbox{\lstinline'sizeof(typeof(*'}e
\mbox{\lstinline')));'}),
\mbox{\lstinline'var_'}n)
}{}
}
{\myinference{$\pi$-valid-read}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\valid_read('}t\mbox{\lstinline')'}) \prule
(I \concat
(l, \mbox{\lstinline'int var_'}n~
\mbox{\lstinline'= __valid_read('}e,\mbox{\lstinline'sizeof(typeof(*'}e
\mbox{\lstinline')));'}),
\mbox{\lstinline'var_'}n)
}{}
}
{\myinference{$\pi$-initialized}
{(l, t:ptr) \trule (I, e) }
{(l, \mbox{\lstinline'\\initialized('}t\mbox{\lstinline')'}) \prule
(I \concat
(l, \mbox{\lstinline'int var_'}n~
\mbox{\lstinline'= __initialized('}e,\mbox{\lstinline'sizeof(typeof(*'}e
\mbox{\lstinline')));'}),
\mbox{\lstinline'var_'}n)
}{}
}
}
\caption{Règles de traduction pour les annotations liées au modèle mémoire}
\label{fig:mem-annots-rules}
\end{figure*}
Afin de pouvoir exploiter les informations sur les blocs stockés dans le
\textit{store}, nous définissons les fonctions \lstinline'__base_addr',
\lstinline'__block_length', \lstinline'__offset', \lstinline'__valid',
\lstinline'__valid_read' et \lstinline'__initialized'.
La sémantique de ces fonctions est conforme à la sémantique des annotations
\eacsl donnée en partie~\ref{sec:mem-annots}.
La fonction \lstinline'__base_addr' retourne l'adresse de début d'un bloc dans
lequel pointe le pointeur qu'elle reçoit en argument.
La fonction \lstinline'__block_length' retourne le nombre d'octets occupés par
le bloc dans lequel pointe le pointeur qu'elle reçoit en argument.
La fonction \lstinline'__offset' retourne le décalage d'un pointeur par rapport
à son adresse de base dans le bloc dans lequel pointe le pointeur qu'elle reçoit
en argument.
Les fonctions \lstinline'__valid' et \lstinline'__valid_read'
retournent le statut de validité à partir d'un pointeur et d'un nombre d'octets.
La fonction \lstinline'__initialized' retourne le statut d'initialisation
d'un nombre d'octets d'un pointeur en argument.
Ces fonctions utilisent les algorithmes~\ref{algo:get-exact}
et~\ref{algo:get-cont} afin de récupérer les informations du {\em store}.
La figure~\ref{fig:mem-annots-rules} présente les règles de traduction des
annotations en utilisant le même formalisme qu'au chapitre~\ref{sec:traduction}.
Nous rappelons que $\tau$ est la fonction de traduction des termes \eacsl et
$\pi$ est la fonction de traduction des prédicats \eacsl.
Dans les règles \textsc{$\pi$-valid}, \textsc{$\pi$-valid-read} et
\textsc{$\pi$-initialized}, \lstinline'typeof(*'$e$\lstinline')' désigne le type
de l'expression \lstinline'*'$e$, qui est un type C tel que \lstinline'int' ou
\lstinline'char'.
\lstinline'sizeof(typeof(*'$e$\lstinline'))' est le nombre d'octets occupés par
un objet de ce type en mémoire.
\section*{Conclusion du chapitre}
Nous avons présenté dans ce chapitre une manière de vérifier dynamiquement les
annotations \eacsl qui concernent la mémoire : \lstinline'\base_addr',
\lstinline'\block_length', \lstinline'\offset', \lstinline'\valid',
\lstinline'\valid_read' et \lstinline'\initialized'.
Nous avons présenté ces annotations, un modèle mémoire permettant de décider de
leur satisfaction ou non à l'exécution, ainsi qu'une manière d'instrumenter le
programme afin de les vérifier à l'exécution.
Rappelons que nous avons choisi de vérifier ces annotations à l'exécution plutôt
que d'utiliser la génération de tests structurels car le modèle mémoire utilisé
par le générateur de tests structurels que nous utilisons n'est pas assez bas
niveau et ne permet donc pas l'exécution symbolique de ces constructions.
Notons que nous avons choisi d'implémenter la notion de {\em store} par des
Patricia tries pour des raisons d'efficacité.
Le chapitre~\ref{sec:eacsl} donne plus de détails concernant cette
implémentation du modèle mémoire ainsi qu'une évaluation de ses performances.