Programmation avancée

Xavier Redon

1 Introduction

1.1 Maquette officielle

Maîtriser le langage C (notamment la gestion mémoire).
Connaître les outils standards de programmation :
- pour pouvoir remplir le rôle de développeur ;
- pour participer à un projet logiciel d’envergure réelle.

1.2 Pédagogie

Approche intégrée :
- séances en salle de travaux pratiques ;
- pas de distinction forte cours / TD / TP.
Approche par la pratique :
- éviter la théorie désincarnée ;
- un système d’exploitation ciblé : Linux ;
- une architecture matérielle ciblée : amd64 ;
- de multiples exercices à réaliser.
Evaluation équilibrée :
- exercices archivés dans un système de gestion de versions ;
- contrôle continu des exercices et de la régularité ;
- un examen final sur machine.

2 Compilation

2.1 Chaîne de compilation 1/5

Code source

#include <stdio.h>
#define MAX 10
#define RESULTAT 0
#define ecrire_entier(e) printf("%d\n",e)
int main(void){
int i;
i=0;
for(i=1;i<=MAX;i++) ecrire_entier(i);
return RESULTAT;
}

Exemples produits avec gcc : http://gcc.gnu.org/
Un compilateur concurrent clang : http://clang.llvm.org/
Exercice "compilateurs" :
- créez un répertoire Compilation ;
- créez deux exécutables différents à partir du source ;
- ce code n’est pas très propre, pourquoi ?
- montrez le avec l’option --dump-tree-cfg-graph et l’utilitaire dot ;
- pensez-vous qu’il nécessaire d’optimiser le code ?
- vérifiez ça avec les options -O et --dump-tree-optimized-graph.

2.2 Chaîne de compilation 2/5

Production du code intermédiaire par :

expansion des macros ;

expansion des fichiers d’entêtes ;

$ gcc -E  prog.c -o prog-cpp.c
$ cat prog-cpp.c 
# 1 "prog.c"
...
# 319 "/usr/include/stdio.h"
...
extern int printf (const char *__restrict __format, ...);
...
# 2 "prog.c" 2
int main(void){
int i;
i=0;
for(i=1;i<=10;i++) printf("%d\n",i);
return 0;
}

création d’un arbre syntaxique abstrait (AST) ;

options pour obtenir l’arbre gcc --dump-tree-xxx ;

$ gcc -Wall --dump-tree-original-raw prog.c
$ ./ast2dot.rb prog.c.003t.original > prog-original.dot
$ dot -Tpng prog-original.dot > prog-original.png

Image originale : prog-ast-full.png

exercice : retrouvez les deux initialisations de i ;

avec un compilateur différent : clang -Xclang -ast-dump -fsyntax-only ;

TranslationUnitDecl 0x9bcb300 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x9bcb5d0 <<invalid sloc>> <invalid sloc> implicit __builtin_va_list 'char *'
|-FunctionDecl 0x9bcb6c0 <prog.c:1:12> col:12 implicit referenced printf 'int (const char *, ...)' extern
| |-ParmVarDecl 0x9bcb720 <<invalid sloc>> <invalid sloc> 'const char *'
| `-FormatAttr 0x9bcb760 <col:12> Implicit printf 1 2
|-FunctionDecl 0x9bcb7a0 prev 0x9bcb6c0 <col:1, col:56> col:12 used printf 'int (const char *, ...)' extern
| |-ParmVarDecl 0x9bcb630 <col:20, col:43> col:43 __format 'const char *restrict'
| `-FormatAttr 0x9bcb820 <col:12> Inherited printf 1 2
`-FunctionDecl 0x9bcb8c0 <line:5:1, line:10:1> line:5:5 main 'int (void)'
  `-CompoundStmt 0x9bcbbf0 <col:15, line:10:1>
    |-DeclStmt 0x9bcb980 <line:6:1, col:6>
    | `-VarDecl 0x9bcb950 <col:1, col:5> col:5 used i 'int'
    |-BinaryOperator 0x9bcb9c0 <line:7:1, col:3> 'int' '='
    | |-DeclRefExpr 0x9bcb990 <col:1> 'int' lvalue Var 0x9bcb950 'i' 'int'
    | `-IntegerLiteral 0x9bcb9a8 <col:3> 'int' 0
    |-ForStmt 0x9bcbba0 <line:8:1, line:4:41>
    | |-BinaryOperator 0x9bcba08 <line:8:5, col:7> 'int' '='
    | | |-DeclRefExpr 0x9bcb9d8 <col:5> 'int' lvalue Var 0x9bcb950 'i' 'int'
    | | `-IntegerLiteral 0x9bcb9f0 <col:7> 'int' 1
    | |-<<<NULL>>>
    | |-BinaryOperator 0x9bcba60 <col:9, line:2:13> 'int' '<='
    | | |-ImplicitCastExpr 0x9bcba50 <line:8:9> 'int' <LValueToRValue>
    | | | `-DeclRefExpr 0x9bcba20 <col:9> 'int' lvalue Var 0x9bcb950 'i' 'int'
    | | `-IntegerLiteral 0x9bcba38 <line:2:13> 'int' 10
    | |-UnaryOperator 0x9bcba90 <line:8:16, col:17> 'int' postfix '++'
    | | `-DeclRefExpr 0x9bcba78 <col:16> 'int' lvalue Var 0x9bcb950 'i' 'int'
    | `-CallExpr 0x9bcbb48 <line:4:26, col:41> 'int'
    |   |-ImplicitCastExpr 0x9bcbb38 <col:26> 'int (*)(const char *, ...)' <FunctionToPointerDecay>
    |   | `-DeclRefExpr 0x9bcbaa4 <col:26> 'int (const char *, ...)' Function 0x9bcb7a0 'printf' 'int (const char *, ...)'
    |   |-ImplicitCastExpr 0x9bcbb80 <col:33> 'const char *' <BitCast>
    |   | `-ImplicitCastExpr 0x9bcbb70 <col:33> 'char *' <ArrayToPointerDecay>
    |   |   `-StringLiteral 0x9bcbae0 <col:33> 'char [4]' lvalue "%d\n"
    |   `-ImplicitCastExpr 0x9bcbb90 <line:8:35> 'int' <LValueToRValue>
    |     `-DeclRefExpr 0x9bcbb04 <col:35> 'int' lvalue Var 0x9bcb950 'i' 'int'
    `-ReturnStmt 0x9bcbbe0 <line:9:1, line:3:18>
      `-IntegerLiteral 0x9bcbbc8 <col:18> 'int' 0

même exercice.

2.3 Chaîne de compilation 3/5

génération de code pour un CPU virtuel ;
GCC utilise Register Transfer Language http://gcc.gnu.org/onlinedocs/gccint/RTL.html ;

options pour obtenir le code RTL gcc --dump-rtl-xxx (e.g. --dump-rtl-expand) ;

(note 1 0 3 NOTE_INSN_DELETED)
(note 3 1 2 2 [bb 2] NOTE_INSN_BASIC_BLOCK)
(note 2 3 4 2 NOTE_INSN_FUNCTION_BEG)
(note 4 2 5 3 [bb 3] NOTE_INSN_BASIC_BLOCK)
(insn 5 4 6 3 (set (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])
        (const_int 0 [0])) prog-cpp.c:4 -1
     (nil))
(insn 6 5 7 3 (set (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])
        (const_int 1 [0x1])) prog-cpp.c:5 -1
     (nil))
(jump_insn 7 6 8 3 (set (pc)
        (label_ref 16)) prog-cpp.c:5 -1
     (nil)
 -> 16)
(barrier 8 7 18)
(code_label 18 8 9 4 3 "" [1 uses])
(note 9 18 10 4 [bb 4] NOTE_INSN_BASIC_BLOCK)
(insn 10 9 11 4 (set (reg/f:SI 59 [ D.1236 ])
        (symbol_ref/f:SI ("*.LC0") [flags 0x2]  <var_decl 0xb726bba0 *.LC0>)) prog-cpp.c:5 -1
     (nil))
(insn 11 10 12 4 (set (reg:SI 62)
        (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])) prog-cpp.c:5 -1
     (nil))
(insn 12 11 13 4 (set (mem:SI (plus:SI (reg/f:SI 56 virtual-outgoing-args)
                (const_int 4 [0x4])) [0 S4 A32])
        (reg:SI 62)) prog-cpp.c:5 -1
     (nil))
(insn 13 12 14 4 (set (mem:SI (reg/f:SI 56 virtual-outgoing-args) [0 S4 A32])
        (reg/f:SI 59 [ D.1236 ])) prog-cpp.c:5 -1
     (nil))
(call_insn 14 13 15 4 (set (reg:SI 0 ax)
        (call (mem:QI (symbol_ref:SI ("printf") [flags 0x41]  <function_decl 0xb7242f00 printf>) [0 S1 A8])
            (const_int 8 [0x8]))) prog-cpp.c:5 -1
     (nil)
    (nil))
(insn 15 14 16 4 (parallel [
            (set (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                        (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])
                (plus:SI (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                            (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])
                    (const_int 1 [0x1])))
            (clobber (reg:CC 17 flags))
        ]) prog-cpp.c:5 -1
     (nil))
(code_label 16 15 17 5 2 "" [1 uses])
(note 17 16 19 5 [bb 5] NOTE_INSN_BASIC_BLOCK)
(insn 19 17 20 5 (set (reg:CCGC 17 flags)
        (compare:CCGC (mem/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
                    (const_int -4 [0xfffffffffffffffc])) [0 i+0 S4 A32])
            (const_int 10 [0xa]))) prog-cpp.c:5 -1
     (nil))
(jump_insn 20 19 21 5 (set (pc)
        (if_then_else (le (reg:CCGC 17 flags)
                (const_int 0 [0]))
            (label_ref 18)
            (pc))) prog-cpp.c:5 -1
     (nil)
 -> 18)
(note 21 20 22 6 [bb 6] NOTE_INSN_BASIC_BLOCK)
(insn 22 21 23 6 (set (reg:SI 60 [ D.1237 ])
        (const_int 0 [0])) prog-cpp.c:6 -1
     (nil))
(insn 23 22 24 6 (set (reg:SI 61 [ <retval> ])
        (reg:SI 60 [ D.1237 ])) prog-cpp.c:6 -1
     (nil))
(jump_insn 24 23 25 6 (set (pc)
        (label_ref 26)) prog-cpp.c:6 -1
     (nil)
 -> 26)
(barrier 25 24 31)
(note 31 25 28 7 [bb 7] NOTE_INSN_BASIC_BLOCK)
(insn 28 31 29 7 (clobber (reg/i:SI 0 ax)) prog-cpp.c:7 -1
     (nil))
(insn 29 28 26 7 (clobber (reg:SI 61 [ <retval> ])) prog-cpp.c:7 -1
     (nil))
(code_label 26 29 32 8 1 "" [1 uses])
(note 32 26 27 8 [bb 8] NOTE_INSN_BASIC_BLOCK)
(insn 27 32 30 8 (set (reg/i:SI 0 ax)
        (reg:SI 61 [ <retval> ])) prog-cpp.c:7 -1
     (nil))
(insn 30 27 0 8 (use (reg/i:SI 0 ax)) prog-cpp.c:7 -1
     (nil))

exercices :
- dans quel segment mémoire se trouve la variable i ?
- à quelle adresse se trouve la variable i ?
- listez les instructions implantant l’instruction for,
- quels sont les registres utilisés pour le for ?
- comment est stocké le format du printf ?
- quels sont les paramètres passés au printf ?
- où sont stockés les paramètres du printf ?
- dans quel registre est stockée la valeur de retour du main ?
clang utilise Intermediate Representation http://llvm.org/docs/LangRef.html ;

option pour obtenir le code RI clang -S -emit-llvm ;

@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 0, i32* %i, align 4
  store i32 1, i32* %i, align 4
  br label %2

; <label>:2
  %3 = load i32* %i, align 4
  %4 = icmp sle i32 %3, 10
  br i1 %4, label %5, label %11

; <label>:5
  %6 = load i32* %i, align 4
  %7 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i32 0, i32 0), i32 %6)
  br label %8

; <label>:8
  %9 = load i32* %i, align 4
  %10 = add nsw i32 %9, 1
  store i32 %10, i32* %i, align 4
  br label %2

; <label>:11
  ret i32 0
}

exercices :
- comment RI traite la notion de pile d’exécution ?
- générez le code RI avec l’option d’optimisation -Os, conclusion ?

2.4 Chaîne de compilation 4/5

Production du code assembleur :

sélection des instructions du CPU cible ;
gestion mémoire : globale, tas et pile ;
éléments d’assembleur x86 :
- w mot (word) de 16 bits, l long mot de 32 bits, q quadruple mot de 64 bits;
- e pour étendu en 32 bits, r pour registre en 64 bits;
- eip est le compteur ordinal (rip en 64 bits);
- esp est le pointeur de pile (rsp en 64 bits);
- l’instruction push empile ;
- l’instruction pop dépile ;
- call <adresse> empile eip (rip en 64 bits) puis le modifie avec <adresse> ;
- ret dépile et modifie eip (rip en 64 bits) avec la valeur dépilée ;
- ebp conserve le sommet de la trame (rbp en 64 bits);
- registres généraux en 32 bits : eax, ebx, ecx, edx, esi, edi ;
- registres généraux en 64 bits : rax, rbx, rcx, rdx, rsi, rdi ;
- registres supplémentaires en 64 bits : r8 à r15.
le schéma de compilation Linux place le résultat dans eax (rax).
placement des paramètres des fonctions sur la pile :
- en 32 bits, paramètres empilés par l’appelant ;
- en 64 bits, paramètres parfois empilés par la fonction ;
- en 64 bits, l’appelant peut stocker les paramètres dans rdi, rsi, rdx, rcx, r8 et r9.

schéma de la pile pour une fonction C :

schéma d’appel Linux 32 bits

schéma d’appel Linux 64 bits, paramètres entiers

Paramètre entrant n	adresses hautes
...
Paramètre entrant 2
Paramètre entrant 1
EIP sauvegarde
EBP sauvegarde	EBP
Variable 1
Variable 2
...
Variable m
Paramètre sortant n’
...
Paramètre sortant 2
Paramètre sortant 1	ESP
	adresses basses

RIP sauvegarde	adresses hautes
RBP sauvegarde	RBP
Variable 1
Variable 2
...
Variable m
...
Paramètre entrant 1 <= RDI
Paramètre entrant 2 <= RSI
...
Paramètre entrant n <= ...
	adresses basses

notre programme simple compilé :

version 32 bits

version 64 bits

$ gcc -Wall -fno-asynchronous-unwind-tables -S prog.c -o prog.s
$ cat prog.s
 .file "prog.c"
 .section .rodata
.LC0:
 .string "%d\n"
 .text
 .globl main
 .type main, @function
main:
 pushl %ebp
 movl %esp, %ebp
 andl $-16, %esp # $-16 -> $0xfffffff0
 subl $32, %esp
 movl $0, 28(%esp)
 movl $1, 28(%esp)
 jmp .L2
.L3:
 movl $.LC0, %eax
 movl 28(%esp), %edx
 movl %edx, 4(%esp)
 movl %eax, (%esp)
 call printf
 addl $1, 28(%esp)
.L2:
 cmpl $10, 28(%esp)
 jle .L3
 movl $0, %eax
 leave
 ret

$ gcc -Wall -fno-asynchronous-unwind-tables -S prog.c -o prog.s64
$ cat prog.s64
 .file   "prog.c"
 .section        .rodata
.LC0:
 .string "%d\n"
 .text
 .globl  main
 .type   main, @function
main:
 pushq   %rbp
 movq    %rsp, %rbp
 subq    $16, %rsp
 movl    $0, -4(%rbp)
 movl    $1, -4(%rbp)
 jmp     .L2
.L3:
 movl    -4(%rbp), %eax
 movl    %eax, %esi
 movl    $.LC0, %edi
 movl    $0, %eax
 call    printf
 addl    $1, -4(%rbp)
.L2:
 cmpl    $10, -4(%rbp)
 jle     .L3
 movl    $0, %eax
 leave
 ret

le programme avec ecrire_entier en tant que fonction :

version 32 bits

version 64 bits

 .file "prog2.c"
 .section .rodata
.LC0:
 .string "%d\n"
 .text
 .globl ecrire_entier
 .type ecrire_entier, @function
ecrire_entier:
 pushl %ebp
 movl %esp, %ebp
 subl $40, %esp
 movl $.LC0, %eax
 movl 8(%ebp), %edx
 movl %edx, 4(%esp)
 movl %eax, (%esp)
 call printf
 movl %eax, -12(%ebp)
 movl -12(%ebp), %eax
 leave
 ret
 .globl main
 .type main, @function
main:
 pushl %ebp
 movl %esp, %ebp
 andl $-16, %esp
 subl $32, %esp
 movl $0, 28(%esp)
 movl $1, 28(%esp)
 jmp .L3
.L4:
 movl 28(%esp), %eax
 movl %eax, (%esp)
 call ecrire_entier
 addl $1, 28(%esp)
.L3:
 cmpl $10, 28(%esp)
 jle .L4
 movl $0, %eax
 leave
 ret

 .file   "prog2.c"
 .section        .rodata
.LC0:
 .string "%d\n"
 .text
 .globl  ecrire_entier
 .type   ecrire_entier, @function
ecrire_entier:
 pushq   %rbp
 movq    %rsp, %rbp
 subq    $32, %rsp
 movl    %edi, -20(%rbp)
 movl    -20(%rbp), %eax
 movl    %eax, %esi
 movl    $.LC0, %edi
 movl    $0, %eax
 call    printf
 movl    %eax, -4(%rbp)
 movl    -4(%rbp), %eax
 leave
 ret
 .size   ecrire_entier, .-ecrire_entier
 .globl  main
 .type   main, @function
main:
 pushq   %rbp
 movq    %rsp, %rbp
 subq    $16, %rsp
 movl    $0, -4(%rbp)
 movl    $1, -4(%rbp)
 jmp     .L4
.L5:
 movl    -4(%rbp), %eax
 movl    %eax, %edi
 movl    $0, %eax
 call    ecrire_entier
 addl    $1, -4(%rbp)
.L4:
 cmpl    $10, -4(%rbp)
 jle     .L5
 movl    $0, %eax
 leave
 ret

exercice "trame de pile" :
- traduisez, via gcc, en assembleur ce programme :
```
 
#include <stdio.h>
void addition(int a,int b){
int c=a+b;
printf("a+b=%d\n",c);
}
int main(void){
addition(1,1);
return 0;
}
```
- dessinez la trame de pile de addition en 32 bits ;
- dessinez la trame de pile de addition en 64 bits.
exercice "compilation manuelle" :
- partez du programme C suivant :
```
 
#include <stdio.h>
unsigned int multiplier(unsigned int a,unsigned int b){
unsigned int resultat;
if(a==0) resultat=0;
else if(a==1) resultat=b;
else resultat=b+multiplier(a-1,b); 
return resultat;
}
int main(void){
unsigned int nombre;
unsigned int a=10,b=20;
nombre=multiplier(a,b);
printf("resultat=%u\n",nombre);
return 0;
}
```
- transformez le code :
  - n’utilisez que affectations et if(...) goto label; ;
  - normalisez les variables
    - pour le schéma 32 bits :
      - renommez les variables locales en ebp_moins_XX
      - renommez les paramètres entrants en ebp_plus_YY ;
      - créez des variables intermédiaires esp_plus_ZZ pour les paramètres sortants ;
      - créez une variable intermédiaire eax pour la valeur de retour.
    - pour le schéma 64 bits avec paramètres entiers :
      - renommez les paramètres entrants en rdi, rsi, ... ;
      - sauvez les paramètres dans des variables rbp_moins_XX
      - renommez les variables locales aussi en rbp_moins_XX
      - renommez les paramètres sortants en rdi, rsi, ... ;
      - créez une variable intermédiaire rax pour la valeur de retour.
- écrivez le code assembleur en partant de :
```
 
 .section .rodata
# ...
 .text
 .globl multiplier
 .type multiplier, @function
multiplier:
# ...
 .globl main
 .type main, @function
main:
# ...
```

2.5 Chaîne de compilation 5/5

Création d’un exécutable ou objet

format "Executable and Linkable" ELF :

 
typedef struct {
    unsigned char e_ident[EI_NIDENT];
    uint16_t      e_type;
    uint16_t      e_machine;
    uint32_t      e_version;
    ElfN_Addr     e_entry;
    ElfN_Off      e_phoff;
    ElfN_Off      e_shoff;
    uint32_t      e_flags;
    uint16_t      e_ehsize;
    uint16_t      e_phentsize;
    uint16_t      e_phnum;
    uint16_t      e_shentsize;
    uint16_t      e_shnum;
    uint16_t      e_shstrndx;
} ElfN_Ehdr;

typedef struct {            typedef struct {
    uint32_t   p_type;          uint32_t   p_type;
    Elf32_Off  p_offset;        uint32_t   p_flags;
    Elf32_Addr p_vaddr;         Elf64_Off  p_offset;
    Elf32_Addr p_paddr;         Elf64_Addr p_vaddr;
    uint32_t   p_filesz;        Elf64_Addr p_paddr;
    uint32_t   p_memsz;         uint64_t   p_filesz;
    uint32_t   p_flags;         uint64_t   p_memsz;
    uint32_t   p_align;         uint64_t   p_align;
} Elf32_Phdr;               } Elf64_Phdr;

typedef struct {                   typedef struct {
    uint32_t   sh_name;                uint32_t   sh_name;
    uint32_t   sh_type;                uint32_t   sh_type;
    uint32_t   sh_flags;               uint64_t   sh_flags;
    Elf32_Addr sh_addr;                Elf64_Addr sh_addr;
    Elf32_Off  sh_offset;              Elf64_Off  sh_offset;
    uint32_t   sh_size;                uint64_t   sh_size;
    uint32_t   sh_link;                uint32_t   sh_link;
    uint32_t   sh_info;                uint32_t   sh_info;
    uint32_t   sh_addralign;           uint64_t   sh_addralign;
    uint32_t   sh_entsize;             uint64_t   sh_entsize;
} Elf32_Shdr;                      } Elf64_Shdr;

sections importantes :
.text :
instructions du programme ;
.bss :
données non initialisées ;
.data :
données initialisées ;
.rodata :
données initialisées en lecture seule ;
.symtab :
table des symboles (entités du programme) ;
.strtab :
noms des symboles de la table des symboles ;
.shstrtab :
noms des sections du fichier ELF ;
.interp :
interpréteur du programme (e.g. chargeur de bibliothéques) ;
.dynamic :
informations concernant les bibliothéques dynamiques ;
.dynsym :
symboles pour les liaison dynamiques ;
.dynstr :
noms des symboles pour les liaison dynamiques ;
.hash :
table pour retrouver rapidement les symboles ;
.got :
table des symboles dynamiques (Global Offset Table) ;
.rel.XXX :
informations de repositionnement ;
YYY.ptl :
indirections pour fonctions dynamiques (Procedure Linkage Table).

exemple d’entête de fichier objet :

 
$ gcc -Wall -fno-asynchronous-unwind-tables -c prog2.c
$ readelf -h prog2.o
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          260 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           40 (bytes)
  Number of section headers:         11
  Section header string table index: 8

liste des sections pour le même exemple :

 
$ readelf -S prog2.o
Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        00000000 000034 00005c 00  AX  0   0  4
  [ 2] .rel.text         REL             00000000 000390 000018 08      9   1  4
  [ 3] .data             PROGBITS        00000000 000090 000000 00  WA  0   0  4
  [ 4] .bss              NOBITS          00000000 000090 000000 00  WA  0   0  4
  [ 5] .rodata           PROGBITS        00000000 000090 000004 00   A  0   0  1
  [ 6] .comment          PROGBITS        00000000 000094 00001e 01  MS  0   0  1
  [ 7] .note.GNU-stack   PROGBITS        00000000 0000b2 000000 00      0   0  1
  [ 8] .shstrtab         STRTAB          00000000 0000b2 000051 00      0   0  1
  [ 9] .symtab           SYMTAB          00000000 0002bc 0000b0 10     10   8  4
  [10] .strtab           STRTAB          00000000 00036c 000023 00      0   0  1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

symboles et repositionnements pour le même exemple :

 
$ readelf -s prog2.o
Symbol table '.symtab' contains 11 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 00000000     0 FILE    LOCAL  DEFAULT  ABS prog2.c
     2: 00000000     0 SECTION LOCAL  DEFAULT    1 
     3: 00000000     0 SECTION LOCAL  DEFAULT    3 
     4: 00000000     0 SECTION LOCAL  DEFAULT    4 
     5: 00000000     0 SECTION LOCAL  DEFAULT    5 
     6: 00000000     0 SECTION LOCAL  DEFAULT    7 
     7: 00000000     0 SECTION LOCAL  DEFAULT    6 
     8: 00000000    34 FUNC    GLOBAL DEFAULT    1 ecrire_entier
     9: 00000000     0 NOTYPE  GLOBAL DEFAULT  UND printf
    10: 00000022    58 FUNC    GLOBAL DEFAULT    1 main
$ readelf -r prog2.o
Relocation section '.rel.text' at offset 0x390 contains 3 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000007  00000501 R_386_32          00000000   .rodata
00000016  00000902 R_386_PC32        00000000   printf
00000045  00000802 R_386_PC32        00000000   ecrire_entier

exemple d’entête de fichier exécutable :

 
$ ld -m elf_i386 -dynamic-linker /lib/ld-linux.so.2 \
     prog2.o /usr/lib/i386-linux-gnu/crt*.o -o prog2 -lc
$ readelf -h prog2
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x804831c
  Start of program headers:          52 (bytes into file)
  Start of section headers:          1524 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         7
  Size of section headers:           40 (bytes)
  Number of section headers:         24
  Section header string table index: 21

exemple de segments pour le même exemple :

 
$ readelf -l prog2
Elf file type is EXEC (Executable file)
Entry point 0x804831c
There are 7 program headers, starting at offset 52

Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
  INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
      [Requesting program interpreter: /lib/ld-linux.so.2]
  LOAD           0x000000 0x08048000 0x08048000 0x00410 0x00410 R E 0x1000
  LOAD           0x000410 0x08049410 0x08049410 0x000e8 0x000e8 RW  0x1000
  DYNAMIC        0x000410 0x08049410 0x08049410 0x000c8 0x000c8 RW  0x4
  NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x4

 Section to Segment mapping:
  Segment Sections...
   00     
   01     .interp 
   02     .interp .note.ABI-tag .hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame 
   03     .dynamic .got .got.plt .data 
   04     .dynamic 
   05     .note.ABI-tag 
   06

2.6 Optimisations du compilateur 1/5

Optimisations à plusieurs étapes :
- les principales sur l’arbre syntaxique (AST) ;
- certaines sur la représentation intermédiaire (RTL/IR).
Plusieurs techniques utilisées
- optimisations directes :
  - substitution de fonctions ;
  - déroulement de boucles ;
  - récursion terminale ;
  - ...
- conversion en affectation unique :
  - propagation de constantes ;
  - élimination de code mort ;
  - diminution de complexité ;
  - factorisation d’expressions ;
  - ...
- flots des données et modèle polyhédrique :
  - parallélisation de boucles ;
  - transformation de boucles ;
  - ...

2.7 Optimisations du compilateur 2/5

Substitutions d’appels de fonctions

exemple de programme :

#include <stdio.h>
int addition(int x,int y){ return x+y; }
int main(void){
int a,b,c;
printf("Donnez 3 entiers\n");
scanf("%d %d %d",&a,&b,&c);
printf("%d\n",addition(a,addition(b,c)));
return 0;
}

compilation avec gcc :

$ gcc -Wall -O2 --dump-tree-einline --dump-tree-optimized \
      substitution.c -o substitution

résultat :

$ cat substitution.c.026t.einline2
main ()
{
  int D.1794,D.1793,D.1793,D.1790,D.1789,D.1789,D.1783,D.1782,D.1780;
  int a,b,c,a.13,b.12,c.11; 
<bb 2>:
  __builtin_puts (&"Donnez 3 entiers"[0]);
  scanf (&"%d %d %d"[0], &a, &b, &c);
  c.11_1 = c;
  b.12_2 = b;
  D.1790_8 = c.11_1 + b.12_2;
  D.1789_10 = D.1790_8;
  D.1780_3 = D.1789_10;
  a.13_4 = a;
  D.1794_9 = D.1780_3 + a.13_4;
  D.1793_11 = D.1794_9;
  D.1782_5 = D.1793_11;
  printf (&"%d\n"[0], D.1782_5);
  D.1783_6 = 0;
  return D.1783_6;
}
$ cat substitution.c.126t.optimized 
main ()
{
  int a,b,c;
<bb 2>:
  __builtin_puts (&"Donnez 3 entiers"[0]);
  scanf (&"%d %d %d"[0], &a, &b, &c);
  printf (&"%d\n"[0], (b + c) + a);
  return 0;
}

exercice : "fonctions imbriquées" :
- créez un répertoire Optimisation ;
- modifiez le programme précédent ;
- transformez addition en soustraction ;
- soustraction doit appeler oppose ;
- vérifiez que les substitutions aient pris place.

Déroulement de boucles

exemple de programme :

#include <stdio.h>
#define TAILLE 10
int main(void){
int a[TAILLE];
int resultat=0;
int i;
for(i=0;i<TAILLE;i++) scanf("%d",&a[i]);
for(i=0;i<TAILLE;i++) resultat += a[i];
return resultat;
}

compilation avec gcc :

$ gcc -Wall -O3 --dump-tree-cunroll --dump-tree-optimized \
      deroulement.c -o deroulement

résultat :

$ cat deroulement.c.126t.optimized 
main ()
{
  int resultat.48;
  int resultat.46;
  int resultat.44;
  int resultat.42;
  int resultat.40;
  int resultat.38;
  int resultat.36;
  int resultat.34;
  int a[10];
<bb 2>:
  scanf (&"%d"[0], &a);
  scanf (&"%d"[0], &a[1]);
  scanf (&"%d"[0], &a[2]);
  scanf (&"%d"[0], &a[3]);
  scanf (&"%d"[0], &a[4]);
  scanf (&"%d"[0], &a[5]);
  scanf (&"%d"[0], &a[6]);
  scanf (&"%d"[0], &a[7]);
  scanf (&"%d"[0], &a[8]);
  scanf (&"%d"[0], &a[9]);
  resultat.34 = a[0] + a[1];
  resultat.36 = resultat.34 + a[2];
  resultat.38 = resultat.36 + a[3];
  resultat.40 = resultat.38 + a[4];
  resultat.42 = resultat.40 + a[5];
  resultat.44 = resultat.42 + a[6];
  resultat.46 = resultat.44 + a[7];
  resultat.48 = resultat.46 + a[8];
  return a[9] + resultat.48;
}

Exercice "calcul du gain" :
- modifiez le programme deroulement.c ;
- ajoutez une seconde dimension au tableau a ;
- remplissez le tableau à l’aide de la fonction rand ;
- rajoutez une boucle pour sommer sur la matrice entière ;
- utilisez l’utilitaire time pour les comparaisons ;
- comparez le temps d’exécution du programme non optimisé ...
- avec le temps d’exécution du programme optimisé -O3 ;
- conclusion ?

Récursion terminale :

exemple de programme :

#include <stdio.h>
int puissance(int a,int b){
if(b==0) return 1;
else return puissance(a,b-1)*a;
}
int main(void){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",puissance(a,b));
return 0;
}

compilation avec gcc :

$ gcc -Wall -O2 --dump-tree-optimized recursion.c -o recursion

résultat :

$ cat recursion.c.126t.optimized 
puissance (a, b)
{
  int mult_acc.13;
<bb 2>:
  if (b == 0) goto <bb 6>; else goto <bb 5>;
<bb 6>:
  mult_acc.13 = 1;
  goto <bb 4>;
<bb 5>:
  mult_acc.13 = 1;
<bb 3>:
  b = b + -1;
  mult_acc.13 = mult_acc.13 * a;
  if (b == 0) goto <bb 4>; else goto <bb 3>;
<bb 4>:
  return mult_acc.13;
}

Exercice "multiplication récursive" :
- modifiez le programme recursion.c ;
- au lieu de calculer une puissance avec des multiplications ...
- ... calculez une multiplication avec des additions ;
- pourquoi l’optimisation est-elle plus aboutie ?

2.8 Optimisations du compilateur 3/5

Mise en affectation unique (SSA) :

chaque variable est affectée au plus une fois ;
il suffit de renommer les variables ;
il faut retrouver les sources dans les expressions ;

un exemple de transformation :

$ cat ssa.c
int main(void){
int a=0;
int b=a;
a=1;
if(a==1) a++;
return a+b;
}
$ gcc -O -Wall --dump-tree-ssa ssa.c -o ssa
$ cat ssa.c.024t.ssa 
main ()
{
  int a,b;
  int D.1196;
<bb 2>:
  a_2 = 0;
  b_3 = a_2;
  a_4 = 1;
  if (a_4 == 1) goto <bb 3>; else goto <bb 4>;
<bb 3>:
  a_5 = a_4 + 1;
<bb 4>:
  # a_1 = PHI <a_4(2), a_5(3)>
  D.1196_6 = a_1 + b_3;
  return D.1196_6;
}

permet des optimisations au vu du nom de la source ;

cette méthode échoue en présence de tableaux :

$ cat ssa3.c
#define TAILLE 1024
int main(void){
int a[TAILLE];
int index=TAILLE/2;
int resultat=0;
int i;
for(i=0;i<TAILLE;i++) a[i]=0;
for(i=0;i<TAILLE;i++) if(i==index) a[i]++;
for(i=0;i<TAILLE;i++) resultat += a[i];
return resultat;
}
$ gcc -O3 -Wall --dump-tree-ssa ssa3.c -o ssa3
$ cat ssa3.c.024t.ssa 
main ()
{
  int i;
  int resultat;
  int index;
  int a[1024];
  int D.1210,D.1209,D.1208;
  int i.0;
...

Elimination de code mort

exemple de programme :

#include <stdio.h>
int main(void){
int a=0;
printf("Coucou !\n");
a=1;
return a;
printf("Caché !\n");
}

compilation avec gcc :

$ gcc -O -Wall --dump-tree-dce code_mort.c -o code_mort

résultat :

$ cat  code_mort.c.079t.dce4 
main ()
{
<bb 2>:
  __builtin_puts (&"Coucou !"[0]);
  a = 1;
  return 1;
}

exercice : trouvez un exemple différent de code mort.

Propagation de constantes

exemple de programme :

int main(void){
int a=1,b=2,c=3;
int d=a*c,e=d+2*b;
if(e!=2) e--;
return e;
}

compilation avec gcc :

$ gcc -O -Wall --dump-tree-ccp propagation.c -o propagation

résultat :

$cat propagation.c.056t.ccp2
main ()
{
<bb 2>:
  return 6;
}

exercice : testez avec un exemple plus complexe.

2.9 Optimisations du compilateur 4/5

Réduction de complexité

exemple de programme :

#include <stdio.h>
#define TAILLE 10
int main(void){
int a[TAILLE];
int i;
int resultat=0;
for(i=0;i<TAILLE;i++) a[i]=TAILLE*i;
for(i=1;i<TAILLE;i++) resultat += a[i]; 
return resultat;
}

compilation avec gcc :

$ gcc -Wall -O --dump-tree-ivopts --dump-tree-optimized \
      complexite.c -o complexite

résultat :

$ cat complexite.c.126t.optimized
main ()
{
  unsigned int ivtmp.36;
  unsigned int ivtmp.34;
  unsigned int ivtmp.25;
  int resultat;
  int a[10];
<bb 2>:
  ivtmp.34 = (unsigned int) &a[0];
  ivtmp.36 = 0;
<bb 3>:
  MEM[index: ivtmp.34] = (int) ivtmp.36;
  ivtmp.34 = ivtmp.34 + 4;
  ivtmp.36 = ivtmp.36 + 10;
  if (ivtmp.34 != (unsigned int) (&a + 40)) goto <bb 3>; else goto <bb 4>;
<bb 4>:
  ivtmp.25 = (unsigned int) &a[1];
  resultat = 0;
<bb 5>:
  resultat = resultat + MEM[index: ivtmp.25];
  ivtmp.25 = ivtmp.25 + 4;
  if (ivtmp.34 != ivtmp.25) goto <bb 5>; else goto <bb 6>;
<bb 6>:
  return resultat;

Factorisation d’expression
- fabriquez l’exemple vous même en écrivant un programme ...
- ... de résolution d’équation du second degré.
- ne tentez pas de factoriser les calculs ;
- compilez avec optimisation et regardez le résultat ;
- le calcul du discriminant est-il factorisé ?
- testez avec l’option -fipa-icf de GCC5.

2.10 Optimisations du compilateur 5/5

Exemple de flots des données

le programme :

origine=0;
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++){ a[i][j]=rand(); b[i][j]=rand(); }
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++) origine += a[i][j]+b[i][j];
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++) a[i][j]=a[i][j]+b[i][j];

le système d’équations :

S0=0;
{ 0<=i<=TAILLE-1, 0<=j<=TAILLE-1 } :
  S1[i,j] = rand();
{ 0<=i<=TAILLE-1, 0<=j<=TAILLE-1 } :
  S2[i,j] = rand();
{ 0<=i<=TAILLE-1, 0<=j<=TAILLE-1 } :
  S3[i,j] =
    ( if(i==0 && j==0) S0;
      else if(j==0) S3[i-1,TAILLE-1];
      else S3[i,j-1]
    ) + S1[i,j] + S2[i,j];
{ 0<=i<=TAILLE-1, 0<=j<=TAILLE-1 } :
  S4[i,j] = S1[i,j] + S2[i,j];

Parallélisation de boucles

exemple de programme :

#include <stdio.h>
#include <stdlib.h>
#define TAILLE 1024
int main(void){
int i,j;
static double a[TAILLE][TAILLE];
static double b[TAILLE][TAILLE];
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++){ a[i][j]=rand(); b[i][j]=rand(); }
float origine=0;
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++) origine += a[i][j]+b[i][j];
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++) a[i][j]=a[i][j]+b[i][j];
float resultat=0;
for(i=0;i<TAILLE;i++) for(j=0;j<TAILLE;j++) resultat += a[i][j];
printf("origine=%lf resultat=%lf\n",origine,resultat);
return 0;
}

compilation avec gcc :

gcc -Wall -O3 --dump-tree-all -ftree-parallelize-loops=2 -floop-parallelize-all \
    matrices.c -o matrices

résultat :

$ cat matrices.c.165t.optimized
main ()
{
...
  .paral_data_store.a = &a;
  .paral_data_store.b = &b;
  __builtin_GOMP_parallel_start (main._loopfn.0, &.paral_data_store, 2);
  main._loopfn.0 (&.paral_data_store);
  __builtin_GOMP_parallel_end ();
...
}

main._loopfn.0 (void * .paral_data_param)
{
// Sommer les lignes de .paral_data_param.a et de .paral_data_param.b
// telles que i % __builtin_omp_get_num_threads() == __builtin_omp_get_thread_num()  
...
}

exercice "architecture multi-coeur" :
- connectez-vous sur une machine avec un gcc récent ;
- trouvez le nombre de coeurs de la machines grâce à /proc/cpuinfo ;
- compilez le programme matrices.c sans aucune optimisation ;
- compilez de façon optimale le programme matrices.c ;
- comparez les temps d’exécution.

2.11 Edition des liens 1/5

Tentons d’éviter l’édition des liens en écrivant ...
... un programme ne nécessitant pas de bibliothèque
Exercice "programme simple" :
- créez un répertoire Edition ;
- écrivez un programme simple.c ;
- le programme doit afficher un texte ;
- compilez votre programme, utilise-t-il une bibliothèque ?
- vérifiez avec ldd et readelf ;
- cherchez les symboles indéfinis avec nm.
Exercice "programme minimal" :
- écrivez un programme minimal.c ;
- le programme doit retourner une valeur ;
- cherchez les symboles indéfinis avec nm ;
- ce programme utilise-t-il encore une bibliothèque ?
- vérifiez avec ldd et readelf.
Exercice "édition des liens manuelle" :
- compilez le programme en deux temps ;
- commencez par générer le fichier objet ;
- tentez l’édition des liens par ld ;
- quel élément manque-t-il ?
- le programme est-il tout de même utilisable ?
Exercice "un peu de hors-piste" :
- remplacez main par _start ;
- la compilation fonctionne-t-elle ?
- l’exécutable fonctionne-t-il ?
L’arrêt d’un programme :
- un programme ne se termine pas par un return ;
- il faut impérativement prévenir le noyau ;
- cela se fait par l’appel système exit ;
- il s’agit de l’appel système 0x01 en 32 bits ;
- ou de l’appel système 60 en 64 bits ;
Exercice "piste noire" :
- écrivez un programme vraiment minimal ;
- essayez avec la fonction _exit ;
- essayez avec la fonction syscall ;
- faut-il passer à l’assembleur ?
  - appel système en 32 bits :
```
__asm__ volatile("int $0x80" : : "a" (syscall), "b" (argument1));
```
  - appel système en 64 bits :
```
__asm__ volatile("syscall" :: "a" (syscall), "D" (argument1) );
```
- examinez l’exécutable avec readelf ;
- avez-vous utilisé une bibliothéque ?
Exercice "épilogue" :
- tentez de réduire la taille de votre exécutable ;
- utilisez les options gcc : -fno-asynchronous-unwind-tables -Qn ;
- utilisez la commande strip ;
- utilisez readelf pour comprendre la compression.

2.12 Edition des liens 2/5

Utilisation de la mémoire :
- constantes => segment .rodata ;
- variables globales initialisées => segment .data ;
- variables globales non initialisées => segment .bss ;
- variables locales => segment [stack] ;
- variables allouées sur le tas => segment [heap].
Exercice "segment pour constante"
- recopiez le programme "piste noire" sous le nom constante.c ;
- définissez dans ce programme une chaîne de caractères ;
- calculez la taille de cette chaîne de caractères ;
- retournez cette taille au système d’exploitation ;
- compilez ce programme pour obtenir un exécutable compact ;
- listez avec readelf la liste des sections.
Exercice "segment pour variable globale initialisée"
- recopiez le programme "piste noire" sous le nom globale.c ;
- définissez dans ce programme une variable globale ;
- retournez cette variable entière au système d’exploitation ;
- compilez ce programme pour obtenir un exécutable compact ;
- listez avec readelf la liste des sections.
Exercice "segment pour variable statique non initialisée"
- recopiez le programme "piste noire" sous le nom statique.c ;
- définissez dans ce programme une fonction ;
- cette fonction comprend une variable entière statique non initialisée ;
- cette variable est retournée par la fonction ;
- retournez au système d’exploitation le résultat de la fonction ;
- compilez ce programme pour obtenir un exécutable compact ;
- quelle valeur est retournée au systéme d’exploitation ?
- listez avec readelf la liste des sections.
Exercice "zone mémoire allouée pour la pile"
- recopiez le programme "piste noire" sous le nom pile.c ;
- utilisez dans ce programme l’appel système sys_nanosleep ;
- en 32 bits :
  - le code de l’appel système est 0xA2 ;
  - le premier paramètre doit être dans %ebx ("b" pour __asm__) ;
  - le second paramètre doit être dans %ecx ("c" pour __asm__).
- en 64 bits :
  - le code de l’appel système est 35 ;
  - le premier paramètre doit être dans %rdi ("D" pour __asm__) ;
  - le second paramètre doit être dans %rsi ("S" pour __asm__).
- le premier paramètre doit être un pointeur du type :
```
struct delai_s { int secondes; int microsecondes; };
```
- initialisez le pour réaliser une attente de 30s ;
- le second paramètre doit être 0 ;
- compilez ce programme pour obtenir un exécutable compact ;
- lancez le programme en tâche de fond ;
- affichez le contenu de /proc/<pid>/maps.
Exercice "zone mémoire allouée pour le tas"
- créez le programme tas.c, ce programme va utiliser la libc ;
- commencez par un main appelant sleep pour dormir 30s ;
- compilez et lancez le programme en tâche de fond ;
- affichez le contenu de /proc/<pid>/maps ;
- ajoutez au programme un appel à malloc pour allouer un octet ;
- faites afficher l’adresse de l’octet et ...
- ... pendant que vous y êtes stockez une valeur dans l’octet ;
- recompilez et relancez le programme en tâche de fond ;
- affichez le contenu de /proc/<pid>/maps ;
- conclusion ? qui gère le tas ?

2.13 Edition des liens 3/5

Bibliothèques statiques
Algorithme d’édition des liens :
- entrée : fichiers objets (variables et fonctions) ;
- entrée : bibliothéques (variables et fonctions) ;
- sortie : un exécutable (chargé par le système) ;
- entités considérées de gauche à droite ;
- 2 ensembles : symboles collectés, symboles indéfinis ;
- si l’entité est un fichier objet F :
  - les symboles exportés par F sont :
    - ajoutés aux symboles collectés ;
    - retranchés des symboles indéfinis.
  - erreur si un même symbole est collecté deux fois ;
  - les symboles importés par F sont :
    - ajoutés aux symboles indéfinis ;
    - sauf si présents comme symboles collectés.
- si l’entité est une bibliothèque B :
  - chaque objet de la bibliothèque est considéré ;
  - si l’objet exporte un symbole indéfini, on le traite ;
  - oubli des objets n’exportant aucun symbole indéfini ;
  - si la liste des symboles indéfinis est modifiée ...
  - ... la bibliothèque est examinée à nouveau.
- quand il ne reste plus d’entité à analyser :
  - erreur s’il reste des symboles indéfinis ;
  - sinon l’exécutable est créé :
    - les sections de même nom sont agrégées ;
    - les agrégats de même type sont agrégés ;
    - une adresse est affectée à chaque agrégat ;
    - les références aux symboles sont calculés.
Création d’une bibliothéque : commande ar
Exercice "programme sans main" :
- écrivez un programme sans fonction main ;
- tentez de le compiler, que se passe-t-il ?
- en utilisant l’option -v de gcc ...
- ... trouvez où se cache le symbole _start.
Exercice "compilation séparée" :
- reprenez le programme multiplier.c ;
- séparez les deux fonctions dans 2 fichiers ;
- fabriquez les deux fichiers objets ;
- générez l’exécutable avec les deux objets ;
- l’ordre des objets est-il important ?
Exercice "ma première bibliothèque" :
- créez une bibliothèque pour la fonction multiplier ;
- compilez le fichier restant avec la bibliothèque ;
- l’ordre entre l’objet et la bibliothèque est-il important ?
- créez une fonction puissance utilisant multiplier ;
- créez une bibliothèque pour la fonction puissance ;
- modifiez le main pour utiliser puissance ;
- compilez le fichier avec les deux bibliothèques ;
- l’ordre des bibliothèques est-il important ?
Exercice "mais en pratique, il fait quoi ld ?" :
- repartez du programme "piste noire" (copié sous le nom embryon.c) ;
- encapsulez l’appel assembleur dans la fonction sortir ;
- dans un fichier ecrire.c créez une autre fonction ;
- la fonction ecrire qui affiche une chaîne de caractères ...
- ... en utilisant l’appel système write (code 0x04 en 32 bits et code 1 en 64 bits) ;
- dans la fonction _start appelez ecrire avant sortir ;
- compilez séparément les deux sources C en ...
- ... utilisant les options pour réduire le nombre de sections ;
- utilisez readelf -x pour afficher les sections .text ;
- que remarquez vous pour le fichier objet embryon.o ?
- utilisez objdump -d pour désassembler le code de embryon.o ;
- utilisez readelf -r pour afficher les repositionnements ;
- pointez les repositionnements dans le code ;
- trouvez l’agrégation effectuée par ld (utilisez readelf -l) ;
- intuitez les déplacements des sections .text et .rodata ;
- comparez avec la réalité (utilisez readelf -s sur l’exécutable) ;
- avec ces données effectuez manuellement les repositionnements ;
- comparez avec la réalité (utilisez objdump -d sur l’exécutable).
Exercice "mieux contrôler ld" :
- lancez ld avec l’option -verbose ;
- comprenez-vous d’où vient le nom du point d’entrée ?
- comprenez-vous d’où vient le décalage du premier segment ?
- écrivez un script plus simple pour ld ...
- en vous basant sur http://sourceware.org/binutils/docs/ld/ ;
- changez le nom du point d’entrée, supprimez le décalage ;
- liez votre programme en utilisant ce script.

2.14 Edition des liens 4/5

Bibliothèques dynamiques
Exécution des programmes à liaisons dynamiques :
- le fichier ELF doit comprendre un segment INTERP ;
- c’est le chargeur dynamique qui est chargé en mémoire :
  - il reçoit un pointeur vers le fichier exécutable ;
  - il charge les segments mémoire de l’exécutable ;
  - il charge les bibliothèques dynamiques non présentes ;
  - il ajoute les segments des bibliothèques dynamiques ...
  - ... à l’espace mémoire virtuelle du processus ;
  - les repositionnements se font par indirection :
    - avec la "Global Offset Table" pour les variables ;
    - avec la "Procedure Linkage Table" pour les fonctions.
  - les repositionnements de fonctions sont calculés dynamiquement ...
  - ... durant l’exécution : on parle de liaison paresseuse.
Exercice de création de bibliothèque dynamique
- créez un fichier libuc.c contenant quelques fonctions ;
- vous pouvez inclure les fonctions ecrire et sortir ;
- compilez le fichier en objet repositionnable avec l’option gcc -fPIC ;
- créez la bibliothèque dynamique avec gcc et l’option -shared ;
- dans un fichier écrivez une fonction _start pour afficher un texte ;
- compilez ce fichier en fichier objet classique ;
- effectuez l’édition des liens avec ld ;
- vérifiez avec ldd que le chargeur dynamique est correct ;
- si ce n’est pas le cas précisez ce chargeur avec l’option -I ;
- ajoutez votre répertoire dans la variable LD_LIBRARY_PATH ;
- vérifiez que votre programme fonctionne en le lançant ;
- lancez ldd sur votre exécutable, pourquoi la libc est listée ?
- affichez la section .dynamic avec readelf -d ;
- quelles informations importantes sont stockées dans cette section ?
- désassemblez l’exécutable avec objdump -d ;
- dans le code de _start vers où pointe l’appel à ecrire ?
- affichez le contenu de .got.plt avec readelf -x ;
- voyez-vous vers où se déroute le saut relatif de ecrire@plt ?
- la fonction du début de la section .plt appelle l’éditeur de lien ;
- quelle résolution va-t-elle être effectuée ? où va être sauvé le résultat ?

2.15 Edition des liens 5/5

Utilisation de bibliothèques dynamiques
Chargement explicite par le programme
Fonctions de bibliothèque :
- dlopen, charge une bibliothèque dynamique ;
- dlsym, récupère un symbole de la bibliothèque ;
- dlclose, décharge éventuellement la bibliothèque ;
- les prototypes :
```
#include <dlfcn.h>

void *dlopen(const char *filename, int flag);
void *dlsym(void *handle, const char *symbol);
int dlclose(void *handle);
```
Exercice "calculatrice modulaire" :
- écrivez un programme bouclant sur la lecture d’opérations ;
- opérations constituées d’un opérateur textuel et 2 opérandes entières ;
- le programme charge la bibliothéque de nom l’opérateur ;
- le symbole calcul est appliqué aux opérandes ;
- le résultat est affiché sur la sortie standard.
Exercice "calculatrice modulaire et efficace" :
- ne fermez plus les bibliothèques après calcul ;
- stockez opérande et symbole dans une liste contigüe ;
- fermez les bibliothèque sur terminaison de l’application.

3 Eléments de programmation C

3.1 Historique 1/4

1966 :

Basic Combined Programming Language (BCPL)

un seul type : le mot machine ;
premier langage à accolades ;

un exemple de programme BCPL :

GET "LIBHDR"

GLOBAL $(
        COUNT: 200
        ALL: 201
$)

LET TRY(LD, ROW, RD) BE
        TEST ROW = ALL THEN
                COUNT := COUNT + 1
        ELSE $(
                LET POSS = ALL & ~(LD | ROW | RD)
                UNTIL POSS = 0 DO $(
                        LET P = POSS & -POSS
                        POSS := POSS - P
                        TRY(LD + P << 1, ROW + P, RD + P >> 1)
                $)
        $)

LET START() = VALOF $(
        ALL := 1
        FOR I = 1 TO 12 DO $(
                COUNT := 0
                TRY(0, 0, 0)
                WRITEF("%I2-QUEENS PROBLEM HAS %I5 SOLUTIONS*N", I, COUNT)
                ALL := 2 * ALL + 1
        $)
        RESULTIS 0
$)

1969 :

Langage B

toujours un langage non typé ;

un exemple de programme B :

main( ) {
  auto c;
  while (1) {
    while ( (c=getchar()) != ' ')
      if (putchar(c) == '*n') exit();
    putchar( '*n' );
    while ( (c=getchar()) == ' '); /* skip blanks */
    if (putchar(c)=='*n') exit(); /* done when newline */
    }
}

1972-1978 :

Brian Kernighan and Dennis Ritchie (KR)

utilisé dès 1972 pour ré-écrire Unix ;
bibliothèque des entrées/sorties (fopen, ...) ;
de nouveaux types (long int, unsigned int) ;
opérateurs composés (e.g. +=) ;

exemple :

/* Exemple de C classique */
/* Compiler par gcc -traditional -Wall kr.c -o kr */
position(string,c)
char *string;
char c;
{
 char *p=string;
 while(*p!=c && *p!='\0') p++;
 if(*p!='\0') return p-string; else return -1;
}
main()
{
 char *string="hello, world";
 printf("w is at %d\n",position(string,'w'));
 printf("A is at %d\n",position(string,'A'));
}

3.2 Historique 2/4

1989 :

Normalisé outre-atlantique ANSI X3.159-1989

1990 :

Normalisé internationalement ISO/IEC 9899:1990

déclaration de paramètres de fonctions à la C++ ;
prototypes de fonctions à la C++ ;
pointeurs void ;
support pour l’internationalisation ;
nouvelles fonctionnalités du pré-processeur ;

exemple :

/* Exemple de C ANSI (c89 ou c90) */
/* Compiler par gcc -ansi -pedantic -Wall ansi.c -o ansi */
#include <stdio.h>
#define suffix(name,suffix) name##suffix
long double suffix(addition,_lg)(long double,void *,int);
int main(void)
{
 long double d=0;
 long double c=10000000.0L;
 float f=1.0; 
 d=suffix(addition,_lg)(d,&c,sizeof c);
 d=suffix(addition,_lg)(d,&f,sizeof f);
 printf("result=%Lf\n",d);
 return 0;
}
long double suffix(addition,_lg)(long double d,void *x,int size)
{
 if(size==sizeof d) d+=*((long double *)x);
 if(size==sizeof(double)) d+=*((double *)x);
 if(size==sizeof(float)) d+=*((float *)x);
 return d;
}

3.3 Historique 3/4

1999 :

Normalisé internationalement ISO/IEC 9899:1999

fonctions inline à substituer textuellement ;
de nouveaux types (long long int, complex, bool, uint16_t, etc) ;
permission de mixer instructions et définitions ;
tableaux de taille variable ;
commentaires à la C++ ;
abandon du type int comme défaut ;

exemple :

// Exemple de c99
// Compiler par gcc -std=c99 -Wall c99.c -o c99
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#define erreur(...) { fprintf(stderr,__VA_ARGS__) ; exit(EXIT_FAILURE); }
int32_t premier(uint32_t n){
bool crible[n*n+1];
for(uint32_t i=0;i<=n*n;i++) crible[i]=true;
for(uint32_t i=2;i<=n;i++)
  if(crible[i]){
    uint32_t j=i*i;
    while(j<=n*n){ crible[j]=false; j += i; }
    }
int32_t result=-1;
for(int32_t i=n*n;i>=0;i--) if(crible[i]){ result=i; break; }
return result;
}
int main(void){
uint32_t n;
if(scanf("%d",&n)!=1) erreur("Echec de lecture du nombre\n");
printf("premier -> %d\n",premier(n));
return 0;
}

exercice : traduisez ce programme en C ANSI.
exercice : manipulation de la pile d’exécution :
- trouvez la taille de la pile par défaut avec ulimit -S -s ;
- trouvez la taille de la pile par défaut avec ulimit -H -s ;
- calculez le plus grand n pouvant être utilisé sans erreur ;
- vérifiez en lançant le programme avec une valeur plus grande ;
- calculez la taille de pile nécessaire pour un n de 3000 ;
- changez la taille de la pile avec la commande ulimit -S -s ;
- essayez aussi avec ulimit -s, que se passe-t-il ?
- relancez le programme avec un n de 3000.

3.4 Historique 4/4

2011 :

Normalisé par "C standards committee"

directives d’alignement des données ;
structure et union anonymes ;
macros polymorphes ;
vérification des limites des tableaux ;
gestion native des threads (indépendant de libpthread) ;
quelques gadgets (_Noreturn, _Atomic, etc) ;

exemple :

// Exemple de c11 (ou c1x)
// Compiler par gcc -std=c1x -Wall c11.c -o c11
//   au 28/02/2014 echec sur _Generic
//   au 17/03/2017 _Generic fonctionne 
// Compiler par clang -std=c1x -Wall c11.c -o c11
//   au 28/02/2014 echec sur _Noreturn, bug sur _Generic
//   au 17/03/2017 fonctionne en cherchant beaucoup
// Echec de verification des limites avec gcc et clang
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
typedef union {
  uint32_t mot;
  struct {
    uint8_t octet1;
    uint8_t octet2;
    uint8_t octet3;
    uint8_t octet4;
    };
  uint8_t octet[4];
  } tranchoir;
#define ecrire(x) \
  printf(_Generic(x,char *:"%s",char[sizeof(x)]:"%s",float:"%f",int:"%d",unsigned char:"%02x"),x)
_Noreturn void die(char *message){ ecrire(message); exit(EXIT_FAILURE); }
int main(void){
uint32_t entier;
ecrire("Donnez un entier :\n");
if(scanf("%x",&entier)!=1) die("Echec de lecture !\n");
tranchoir t;
t.mot=entier;
ecrire("O"); ecrire(1); ecrire("="); ecrire(t.octet1); ecrire("\n");
ecrire("O"); ecrire(2); ecrire("="); ecrire(t.octet2); ecrire("\n");
ecrire("O"); ecrire(3); ecrire("="); ecrire(t.octet3); ecrire("\n");
ecrire("O"); ecrire(4); ecrire("="); ecrire(t.octet4); ecrire("\n");
for(uint8_t i=0;i<=4;i++)
 { ecrire("O"); ecrire(i); ecrire("="); ecrire(t.octet[i]); ecrire(i==3?"\n":", "); }
return 0;
}

une exécution :

$ ./c11
Donnez un entier :
ca11efa5
O00=a5, O01=ef, O02=11, O03=ca

3.5 Quelques révisions 1/3

Extraits de http://www.slideshare.net/olvemaudal/deep-c

Type de la fonction principale :

 
#include <stdlib.h>
main(void){ exit(0); }

 
$ gcc main.c -o main
$ gcc -std=c99 main.c -o main
/tmp/main.c:2:1: warning: return type defaults to ‘int’
 main(void){ exit(0); }

Valeur par défaut des fonctions :

 
int main(void){ }

 
$ gcc -Wall -ansi retour.c -o retour_ansi
retour.c: In function ‘main’:
retour.c:1:1: warning: control reaches end of non-void function [-Wreturn-type]
$ gcc -Wall -std=c99 retour.c -o retour_c99
$ gcc -Wall retour.c -o retour
retour.c: In function ‘main’:
retour.c:1:1: warning: control reaches end of non-void function [-Wreturn-type]
$ ./retour_ansi ; echo $?
212
$ ./retour_c99 ; echo $?
0

Déclaration implicite :

 
int main(void){
printf("Bonjour !\n");
return 0;
}

 
$ clang -Wall implicite.c -o implicite
implicite.c:2:1: warning: implicitly declaring C library function 'printf' with type 'int (const char *, ...)'
implicite.c:2:1: note: please include the header <stdio.h> or explicitly provide a declaration for 'printf'
$ g++ -Wall implicite.c -o implicite
implicite.c: In function ‘int main()’:
implicite.c:2:35: error: ‘printf’ was not declared in this scope

3.6 Quelques révisions 2/3

De l’utilité du vide :

 
#include <stdio.h>
#include <string.h>
#ifdef PROTOTYPE_INCOMPLET
int f();
#endif
#ifdef PROTOTYPE_COMPLET
int f(void);
#endif
int main(void){
printf("%d\n",f("abc"));
return 0;
}
int f(void){ return 42; }

 
$ gcc -std=c99 -Wall void.c -o void
void.c: In function ‘main’:
void.c:10:1: warning: implicit declaration of function ‘f’ [-Wimplicit-function-declaration]
$ gcc -Wall -DPROTOTYPE_INCOMPLET void.c -o void
$ gcc -Wall -DPROTOTYPE_COMPLET void.c -o void
void.c: In function ‘main’:
void.c:10:1: error: too many arguments to function

Les variables globales sont initialisées :

 
#include <stdio.h>
int v1;
int f(void){ static int v2; return v2++; }
int main(void){
int v3;
printf("v1=%d\n",v1);
printf("v2=%d\n",f());
printf("encore v2=%d\n",f());
printf("v3=%d\n",v3);
return 0;
}

 
$ gcc -Wall init.c -o init
init.c: In function ‘main’:
init.c:9:7: warning: ‘v3’ is used uninitialized in this function [-Wuninitialized]
$ ./init
v1=0
v2=0
encore v2=1
v3=-1215623180

3.7 Quelques révisions 3/3

Notion de limites de séquence en C :
- limites créées par les opérateurs &&, || et , ;
- limite créée par l’opérateur ? des expressions conditionnelles ;
- une limite, bien sur, en fin d’instruction ;
- une limite entre l’évaluation des arguments et l’appel d’une fonction ;
- une limite après chaque initialisation de variable.
Une seule affectation à V entre deux limites de séquence.
Si affectation à V pas de lecture de V hormis pour cette affectation.

Exemple de programme avec des expressions non définies :

 
#include <stdio.h>
int v1;
int f(int v2){ return v1+v2; }
int main(void){
int v3=v1++,v4=v1;
printf("v3=%d v3=%d\n",v3++,v3);
printf("v4=%d\n",v4);
printf("f=%d\n",f(v1++));
v1=v1++;
printf("v1=%d\n",v1);
return 0;
}

 
$ gcc -Wall effets.c -o effets
effets.c: In function ‘main’:
effets.c:6:26: warning: operation on ‘v3’ may be undefined [-Wsequence-point]
effets.c:9:3: warning: operation on ‘v1’ may be undefined [-Wsequence-point]
$ ./effets
v3=0 v3=1
v4=1
f=3
v1=3

Exercice : trouvez d’autres exemples d’expressions illégales.

Taille des types et alignements :

 
#include <stdio.h>
typedef struct truc_s { char c1; char c2 ; int e1; long int e2; } truc_t;
int main(void){
truc_t t;
printf("taille=%d(%d)\n",(int)sizeof t,(int)sizeof(struct truc_s));
return 0;
}

 
tutur01$ arch ; ./tailles
i686
taille=12(12)
zabeth14$ arch ; ./tailles
x86_64
taille=16(16)

Exercice : testez si le système est petit ou gros boutiste.

3.8 Communication avec le système

Récupération des arguments :

// Affiche les arguments d'un programme C
// Compiler avec gcc -Wall -g -std=c99 -o arguments arguments.c

#include <stdio.h>

int main(int argc,char *argv[]){
printf("Nombre d'arguments : %d\n",argc);
printf("Chemin de l'exécutable : '%s'\n",argv[0]);
for(int i=1;i<argc;i++)
  printf("Argument n°%d : '%s'\n",i,argv[i]);
return 0;
}

Exemple d’exécution :

$ ./arguments un dix "vingt et un"
Nombre d'arguments : 4
Chemin de l'exécutable : './arguments'
Argument n°1 : 'un'
Argument n°2 : 'dix'
Argument n°3 : 'vingt et un'

Récupération des variables d’environnement :

// Affiche les variables d'environnement
// Compiler avec gcc -Wall -g -std=c99 -o variables variables.c

#include <stdio.h>
#include <stdlib.h>

#define MAX_NOM         1024

extern char **environ;

int main(void){
while(*environ!=NULL){
  char nom[MAX_NOM];
  if(sscanf(*environ,"%[^=]",nom)==1)
    printf("Variable %s -> '%s'\n",nom,getenv(nom));
  environ++;
  }
return 0;
}

Valeur de retour :

// Implante les executables true et false
// Compiler avec gcc -Wall -g -o booleen booleen.c
// Installer avec ln -s booleen true; ln -s booleen false

#include <stdio.h>
#include <string.h>

int main(int argc,char *argv[]){
char *base=strrchr(argv[0],'/');
if(base==NULL) base=argv[0];
if(strcmp(base,"true")==0) return 0; else return 1;
}

Exemple d’exécution :

$ true ; echo $?
0
$ false ; echo $?
1
$ if true ; then echo VRAI ; else echo FAUX ; fi
VRAI
$ if false ; then echo VRAI ; else echo FAUX ; fi
FAUX

3.9 Allocation mémoire

Gestion du tas
Segment mémoire classique
Fonctions de bibliothéque :
- malloc, réservation d’octets sur le tas ;
- calloc, réservation et initialisation d’éléments ;
- realloc, modification de la taille de bloc mémoire ;
- free, libération de bloc réservé.
- les prototypes :
```
#include <stdlib.h>

void *calloc(size_t nmemb, size_t size);
void *malloc(size_t size);
void free(void *ptr);
void *realloc(void *ptr, size_t size);
```

De l’inutilité de la coercition en C ANSI :

#include <stdio.h>
#include <stdlib.h>
int main(void){ int *n=malloc(sizeof(int)); *n=42; return *n; }

Implantation par la libc :
- des blocs alloués ou libérés ;
- l’entête des blocs contient sa taille ;
- les blocs sont chaînés entre eux ;
- les blocs peuvent être fragmentés ;
- les blocs peuvent être fusionnés.
Exercice "Liste contigüe dynamique" :
- créez un sous-répertoire Allocation ;
- partons sur la base d’une liste d’entiers ;
- définissez une structure contenant :
  - un pointeur sur un tableau d’entier ;
  - la taille courante de la liste ;
  - le nombre d’entiers alloués.
- écrivez une fonction d’initialisation de liste ;
- écrivez une fonction d’ajout d’élément dans la liste ;
- écrivez une fonction d’accès à un élément dans la liste ;
- la procédure principale enchaine :
  - l’ajout d’un élément dans la liste ;
  - l’affichage d’un élément de la liste.

3.10 Fichiers, principes

Fichiers binaires

$ od -Ax -tx1 /boot/boot.0800
000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
0001b0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01
0001c0 01 00 83 fe bf 28 3f 00 00 00 aa 8e 87 00 00 00
0001d0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
*
0001f0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 55 aa
000200
$

Fichiers textes

$ od -Ax -tx1 /etc/motd      
000000 0a 42 69 65 6e 76 65 6e 75 65 20 73 75 72 20 6c
000010 65 73 20 6d 61 63 68 69 6e 65 73 20 64 65 20 50
000020 6f 6c 79 74 65 63 68 27 4c 69 6c 6c 65 2e 0a 0a
000030
$ od -Ax -tx1 /mnt/Window/win.ini
000000 3b 20 66 6f 72 20 31 36 2d 62 69 74 20 61 70 70
000010 20 73 75 70 70 6f 72 74 0d 0a 5b 66 6f 6e 74 73
000020 5d 0d 0a 5b 65 78 74 65 6e 73 69 6f 6e 73 5d 0d
000030 0a 5b 6d 63 69 20 65 78 74 65 6e 73 69 6f 6e 73
000040 5d 0d 0a 5b 66 69 6c 65 73 5d 0d 0a 5b 4d 61 69
000050 6c 5d 0d 0a 4d 41 50 49 3d 31 0d 0a
00005c

Types de fichiers Unix :
.
fichiers classiques ;
d
fichiers répertoires ;
l
liens symboliques ;
s
socket ;
c
fichier spécial caractére ;
b
fichier spécial bloc.

3.11 Fichiers, bas niveau 1/3

Utilisation de primitives
Fichier référencé par un descripteur

Ouverture et fermeture :

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int open(const char *pathname,int flags,mode_t mode);
int close(int fd);

Lecture et écriture :

#include <unistd.h>

ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);

Déplacement dans le fichier :

#include <sys/types.h>
#include <unistd.h>

off_t lseek(int fd, off_t offset, int whence);

Configuration de l’entité correspondante :

#include <sys/ioctl.h>

int ioctl(int d, int request, ...);

3.12 Fichiers, bas niveau 2/3

Exemple "copie de fichiers" :

// Programme de copie de fichiers
// Compiler avec : gcc -Wall -g copie.c -o copie

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define MAX_BLOC        2048

int main(int argc,char *argv[]){
if(argc!=3){
  fprintf(stderr,"Syntaxe : %s <original> <copie>\n",argv[0]);
  exit(EXIT_FAILURE);
  }
char *original=argv[1];
char *copie=argv[2];
int dorig=open(original,O_RDONLY);
if(dorig<0){
  fprintf(stderr,"Impossible d'ouvrir '%s' en lecture !\n",original);
  exit(EXIT_FAILURE);
  }
int dcopie=open(copie,O_WRONLY|O_CREAT|O_TRUNC,S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH);
if(dcopie<0){
  fprintf(stderr,"Impossible d'ouvrir '%s' en écriture !\n",copie);
  exit(EXIT_FAILURE);
  }
int taille;
unsigned char bloc[MAX_BLOC];
while((taille=read(dorig,bloc,MAX_BLOC))>0)
  if(write(dcopie,bloc,taille)!=taille){
    fprintf(stderr,"Echec d'écriture sur '%s' !\n",copie);
    exit(EXIT_FAILURE);
    }
close(dorig);
close(dcopie);
return 0;
}

3.13 Fichiers, bas niveau 3/3

Exercice "communication série" :
- commencez par connecter l’Arduino au PC ;
- listez les fichiers de préfixe /dev/tty[A-Z] ;
- quel fichier correspond à la connexion série avec l’Arduino ?
- configurez la vitesse de la connexion série avec stty :
```
$ stty -F /dev/ttyACM0 9600 cs8 \
  -hupcl -icrnl -ixon -opost -onlcr -isig -icanon \
  -iexten -echo -echoe -echok -echoctl -echoke ignbrk
```
- écrivez un programme affichant les caractères ...
- ... envoyés par l’Arduino (liés aux aux boutons pressés) ;
- envoyez à l’Arduino un caractère entre ’1’ et ’6’ ;
- quel est l’effet sur la platine Arduino ?
- faites en sorte qu’à chaque fois qu’un bouton est utilisé ...
- ... la LED associée soit allumée.
Exercice "répertoire Unix" :
- tentez de lire un répertoire par open, read et close ;
- n’oubliez pas d’afficher d’éventuelles erreurs par perror ;
- recommencez avec les fonctions opendir, readdir et closedir ;
- affichez les numéros d’i-noeuds et les noms des fichiers du répertoire.

3.14 Fichiers, haut niveau 1/3

Utilisation de fonctions de bibliothèque stdio.h
Fichier référence par une structure FILE ;

Ouverture et fermeture :

#include <stdio.h>

FILE *fopen(const char *path, const char *mode);
FILE *fdopen(int fd, const char *mode);
int fclose(FILE *fp);

Lecture et écriture :

#include <stdio.h>

int fprintf(FILE *stream, const char *format, ...);
int fscanf(FILE *stream, const char *format, ...);
char *fgets(char *s, int size, FILE *stream);
size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream);
size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream);

Déplacement dans le fichier :

#include <stdio.h>

int fseek(FILE *stream, long offset, int whence);
long ftell(FILE *stream);
void rewind(FILE *stream);

3.15 Fichiers, haut niveau 2/3

Exemple "conversion de fichiers" :

// Programme de conversion de fichiers
// Compiler avec : gcc -Wall -g conversion.c -o conversion

#include <stdio.h>
#include <stdlib.h>

#define FORMAT_CHAINE           "%%%ds %%f %%%ds %%c %%%d[^\n]"
#define FORMAT_NOMBRE           5

#define TAILLE_COMPTE           16
#define TAILLE_DATE             16
#define TAILLE_COMMENTAIRE      64

#define MAX_FORMAT              64
#define MAX_LIGNE               1024

typedef struct {
  char compte[TAILLE_COMPTE];
  float somme;
  char date[TAILLE_DATE];
  char etat;
  char commentaire[TAILLE_COMMENTAIRE];
  } enregistrement;

int main(int argc,char *argv[]){
if(argc!=3){
  fprintf(stderr,"Syntaxe : %s <fichier texte> <fichier binaire>\n",argv[0]);
  exit(EXIT_FAILURE);
  }
char *texte=argv[1];
char *binaire=argv[2];
FILE *ftexte=fopen(texte,"r");
if(ftexte==NULL){
  fprintf(stderr,"Impossible d'ouvrir '%s' en lecture !\n",texte);
  exit(EXIT_FAILURE);
  }
FILE *fbinaire=fopen(binaire,"w+");
if(fbinaire==NULL){
  fprintf(stderr,"Impossible d'ouvrir '%s' en écriture !\n",binaire);
  exit(EXIT_FAILURE);
  }
char format[MAX_FORMAT];
sprintf(format,FORMAT_CHAINE,TAILLE_COMPTE-1,TAILLE_DATE-1,TAILLE_COMMENTAIRE-1);
char ligne[MAX_LIGNE];
while(fgets(ligne,MAX_LIGNE,ftexte)!=NULL){
  enregistrement e;
  int nombre=sscanf(ligne,format,e.compte,&e.somme,e.date,&e.etat,&e.commentaire);
  if(nombre!=FORMAT_NOMBRE){
    fprintf(stderr,"Mauvais format : %s",ligne);
    exit(EXIT_FAILURE);
    }
  if(fwrite(&e,sizeof e,1,fbinaire)!=1){
    fprintf(stderr,"Echec d'écriture sur '%s' !\n",binaire);
    exit(EXIT_FAILURE);
    }
  }
fclose(ftexte);
fclose(fbinaire);
return 0;
}

3.16 Fichiers, haut niveau 3/3

Exercice "gestion de comptes" :
- un fichier est une suite d’enregistrements ;
- même structure que dans le programme d’exemple ;
- le tableau est sauvé dans un fichier binaire ;
- un exécutable pour modifier ou ajouter un élément ;
- pour modifier il faut spécifier le rang de l’enregistrement ;
- un exécutable pour récupérer un élément ;
- l’élément est récupéré par son rang ou un mot du commentaire ;
- utiliser un lien symbolique.
Exercice "analyse de la description de l’AST de gcc".

Exercice "Conversion de fichiers STL" :

un fichier STL ASCII est de la forme :

solid name
...
facet normal ni nj nk
    outer loop
        vertex v1x v1y v1z
        vertex v2x v2y v2z
        vertex v3x v3y v3z
    endloop
endfacet
...
endsolid name

un fichier STL binaire = structure entête + tableau de structures triangle :

struct STL_header_s {
  uint8_t void[80];
  uint32_t nb_triangles;
  } 
struct STL_triangle_s {
  float n[3];
  float v1[3];
  float v2[3];
  float v3[3];
  uint16_t count;
  }

Ecrivez un programme de conversion STL ASCII vers binaire.

4 Outils de développement

4.1 Gestion de versions

Deux objectifs :
- gestion des versions de sources ;
- orchestration d’un groupe d’intervenants.
Large choix d’outils :
- Concurrent Versions System (CVS), l’ancêtre ;
- Apache Subversion (SVN), compatible CVS ;
- GIT, décentralisé, très rapide ;
- Mercurial, concurrent de GIT.
Outil GIT fondé par Linus Torvald :
- architecture distribuée (pas forcément de serveur) ;
- efficace pour les divergences et les convergences ;
- optimisé : rapide et économe ;
- utilise les protocoles réseaux existants.
Hiérarchie des niveaux sous GIT :
- éventuellement un dépôt distant ;
- votre dépôt local :
  - votre répertoire de travail ;
  - l’index (répertoire .git) ;
  - le dépôt (répertoire .git).
Exercice "création d’un dépot" (version locale) :
- dans un répertoire vide archive, initialisation par git init ;
- l’état de l’archive peut être affichée par git status ;
- renseignez votre nom et votre courriel par les commandes ...
- git config --global user.name "Prénom Nom" et ...
- ... git config --global user.email "courriel" ;
- liste des fichiers dans l’index par git ls-files ;
- liste des fichiers dans le dépôt par git ls-tree -r HEAD ;
- créez un dépôt vide par git commit --allow-empty -m "Archive vide" ;
- créez un fichier de travail, listez l’index, listez le dépôt, conclusion ?
- vous pouvez lister les fichiers de travail non indexés : git ls-files --other ;
- ajoutez le fichier à l’index par git add, listez index et dépôt, conclusion ?
- ajoutez le fichier dans le dépôt par git commit -m, listez index et dépôt, conclusion ?
Exercice "création d’un dépôt" (version serveur ssh) :
- connectez vous sur une machine de projet par ssh ;
- créez un répertoire, placez-vous dans ce répertoire ;
- créez votre dépôt par la commande git init --bare ;
- sur la machine de TP, créez un dépôt de travail par ...
- git clone ssh://utilisateur@serveur/~utilisateur/depot ;
- entrez dans le dépôt, créez un fichier lisezmoi ;
- insérez le fichier dans l’index git add lisezmoi ;
- validez vos modifications localement git commit ;
- téléversez vos modifications git push origin master ;
- clonez le dépôt dans un autre espace ;
- modifiez lisezmoi dans les deux espaces ;
- tentez de téléverser aprés validation locale ;
- résolvez le conflit !
Exercice "création d’un dépôt" (version application gitlab) :
- visualisez la page https://archives.plil.fr avec un navigateur ;
- connectez vous à gitlab avec vos identifiants école ;
- créez un dépôt privé pour le module de programmation avancé ;
- sous votre compte de TP, créez une clef asymétrique avec ssh-keygen -t rsa ;
- importez la clef publique ~/.ssh/id_rsa.pub pour votre dépôt ;
- créez un dépôt de travail via ssh par la commande ...
- ... git clone git@archives.plil.fr:<login>/programmation_avancee.git ;
- entrez dans le dépôt, créez un fichier lisezmoi ;
- insérez le nouveau fichier dans l’index avec git add lisezmoi ;
- validez vos modifications localement git commit -m "exercice git" ;
- téléversez vos modifications vers gitlab avec git push ;
- sur une machine de projet, configurez votre nom et courriel ;
- créez un dépôt de travail via https par la commande ...
- ... git clone https://<login>@archives.plil.fr/<login>/programmation_avancee.git ;
- modifiez le fichier lisezmoi dans les deux dépôts de travail ;
- tentez de pousser vos modifications aprés validation locale ;
- résolvez le conflit (et jouez un peu avec gitlab) !
Exercice "branches et fusion" :
- créez une branche dans votre archive par git branch <branche> ;
- basculez vers votre nouvelle branche par git checkout <branche> ;
- créez un répertoire GIT_branche dans la nouvelle branche ;
- modifiez le fichier lisezmoi dans la nouvelle branche ;
- ajoutez un fichier dans le répertoire GIT_branche ;
- mettez à jour le dépôt distant ;
- basculez vers la branche principale par git checkout master ;
- que constatez-vous dans votre répertoire de travail ?
- créez un répertoire GIT_master dans la branche principale ;
- modifiez le fichier lisezmoi dans la branche principale ;
- ajoutez un fichier dans le répertoire GIT_master ;
- basculez vers la branche annexe, que constatez-vous ?
- revenez dans la branche principale, fusionnez par git merge <branche> ;
- affichez l’historique des branches par git show-branch.
Exercice "versions" :
- posez une étiquette sur votre archive par git tag -a "v0.1" ;
- créez un répertoire GIT_version, créez-y un fichier ;
- mettez à jour le dépôt distant ;
- posez une seconde étiquette par git tag -a "v0.2" ;
- mettez à jour les étiquettes le dépôt distant par git push --tags ;
- listez les étiquettes par git tag ;
- récupérez l’archive dans un autre répertoire ;
- vérifiez que vous avez bien les fichiers de la version v0.2 ;
- basculez sur la version v0.1 par git checkout v0.1.

4.2 Automatisation de la compilation 1/4

Outil Makefile (version GNU).
Automatisation de génération de projets.
Exercice "utilisation sans fichier de configuration" :
- créez un répertoire Automatisation dans votre dépôt ;
- récupérez le source prog.c du chapitre compilation ;
- utilisez make pour générer directement l’exécutable ;
- utilisez make pour générer le fichier objet ;
- utilisez make pour effectuer l’édition des liens.

4.3 Automatisation de la compilation 2/4

Un fichier de configuration par défaut [Mm]akefile :

tabulations impératives !

des variables :

OBJETS = puissance.o multiplier.o
BIBLIOTHEQUE = operations.a
AR = ar r
CFLAGS += -Wall -g

des cibles (cible, dépendance, action) :

$(BIBLIOTHEQUE): $(OBJETS)
        $(AR) $(BIBLIOTHEQUE) $(OBJETS)

puissance.o: puissance.c
        $(CC) $(CFLAGS) -c puissance.c

multiplier.o: multiplier.c
        $(CC) $(CFLAGS) -c multiplier.c

des variables automatiques :

$(BIBLIOTHEQUE): $(OBJETS)
        $(AR) $@ $+

des règles implicites :

%.o: %.c
        $(CC) -c $(CFLAGS) $(CPPFLAGS) $< -o $@

4.4 Automatisation de la compilation 3/4

Configuration pour créer un exécutable :

SOURCES = $(wildcard *.c)
OBJETS = $(SOURCES:.c=.o)
BIBLIOTHEQUES = -L ../Localbib -lbib
EXECUTABLE = projet
CFLAGS += -Wall -I ../Localbib

all: $(EXECUTABLE)

$(EXECUTABLE): $(OBJETS)
        $(CC) -o $@ $^ $(BIBLIOTHEQUES)

clean:
        rm -rf $(EXECUTABLE) *.o

Configuration pour créer une bibliothèque :

SOURCES = $(wildcard *.c)
OBJETS = $(SOURCES:.c=.o)
BIBLIOTHEQUE = libbib.a
AR = ar r
CFLAGS += -Wall

all: $(BIBLIOTHEQUE)

$(BIBLIOTHEQUE): $(OBJETS)
        $(AR) $@ $^

$(OBJETS): bibliotheque.h

clean:
        rm -rf *.o *.a core

4.5 Automatisation de la compilation 4/4

Configuration pour un projet complet :

REPERTOIRES = Main Bibliotheque
COMPILE = $(REPERTOIRES:%=all-%)
DEVERMINE = $(REPERTOIRES:%=debug-%)
NETTOYAGE = $(REPERTOIRES:%=clean-%)
export CFLAGS += -Wall 

all: $(COMPILE)
$(COMPILE):
        $(MAKE) -C $(@:all-%=%)

debug: $(DEVERMINE)
$(DEVERMINE): CFLAGS += -g -DDEVERMINE
$(DEVERMINE):
        $(MAKE) -C $(@:debug-%=%)

clean: $(NETTOYAGE)
$(NETTOYAGE):
        $(MAKE) -C $(@:clean-%=%) clean

all-Main: all-Bibliotheque
debug-Main: debug-Bibliotheque

.PHONY: $(COMPILE) $(DEVERMINE) $(NETTOYAGE)
.PHONY: all debug clean

Exercice "la totale" :
- créez un sous-répertoire ProjetCalcul ;
- créez deux sous-sous-répertoires Operations et Calcul ;
- récupérez les sources de votre première bibliothéque ...
- ... multiplier et puissance formeront une unique bibliothèque ;
- créez un fichier d’entêtes .h dans le répertoire Operations ;
- écrivez la configuration de création de la bibliothèque dans Operations ;
- écrivez la configuration de création de l’éxecutable dans Calcul ;
- écrivez la configuration du projet complet dans ProjetCalcul ;
- testez vos configuration par la commande make clean all.

4.6 Déverminage 1/4

Outil gdb : GNU Debugger.
Une interface graphique à gdb : ddd.
Prendre soin de compiler avec gcc -g.

Exemple de session gdb :

$ gcc -Wall -g segfault.c -o segfault
$ gdb ./segfault
GNU gdb 6.8-debian
...
(gdb) run
Starting program: ./segfault 

Program received signal SIGSEGV, Segmentation fault.
0xb77ee9b7 in memcpy () from /lib/libc.so.6
(gdb) backtrace
#0  0xb77ee9b7 in memcpy () from /lib/libc.so.6
#1  0x08048400 in main () at segfault.c:6
(gdb) list
1 #include <stdio.h>
2 #include <string.h>
3 
4 int main(void){
5 char *chaine;
6 strcpy(chaine,"Bouuuuuuuum !!!!!!!");
7 printf("%s\n",chaine);
8 return 0;
9 }
(gdb) break 6
Breakpoint 1 at 0x80483e5: file segfault.c, line 6.
(gdb) run
The program being debugged has been started already.
Start it from the beginning? (y or n) y
Starting program: ./segfault 

Breakpoint 1, main () at segfault.c:6
6 strcpy(chaine,"Bouuuuuuuum !!!!!!!");

(gdb) (gdb) print/x chaine
$4 = 0xb7717775
(gdb) quit
The program is running.  Exit anyway? (y or n) y

4.7 Déverminage 2/4

Exemple plus complexe de session gdb :

$ gcc -Wall -g boucle.c -o boucle
$ gdb ./boucle
GNU gdb 6.8-debian
...
(gdb) break main
Breakpoint 1 at 0x80483c2: file boucle.c, line 9.
(gdb) run
Starting program: ./boucle 

Breakpoint 1, main () at boucle.c:9
9 for(i=0;i<10;i++) tab[i]=carre(i);
(gdb) watch i
Hardware watchpoint 3: i
(gdb) continue
Continuing.
Hardware watchpoint 4: i

Old value = 134513753
New value = 0
0x080483e1 in main () at boucle.c:9
9 for(i=0;i<10;i++) tab[i]=carre(i);
(gdb) c
Continuing.
Hardware watchpoint 4: i

Old value = 0
New value = 1
0x080483e1 in main () at boucle.c:9
9 for(i=0;i<10;i++) tab[i]=carre(i);
(gdb) next
Hardware watchpoint 4: i

Old value = 2
New value = 3
0x080483e1 in main () at boucle.c:9
9 for(i=0;i<10;i++) tab[i]=carre(i);
(gdb) step
carre (n=4) at boucle.c:4
4 int carre(int n){ return n*n; }
(gdb) print n
$3 = 3
(gdb) c
Continuing.
Hardware watchpoint 4: i

Old value = 3
New value = 4
0x080483e1 in main () at boucle.c:9
9 for(i=0;i<10;i++) tab[i]=carre(i);
(gdb) print i
$4 = 4
(gdb) quit
The program is running.  Exit anyway? (y or n) y

4.8 Déverminage 3/4

Exemple de session avec ddd :

4.9 Déverminage 4/4

Une autre session avec ddd :
Création de la cellule

Queue de liste rattachée à la cellule

Tête de la liste mise à jour

4.10 Vérificateur mémoire 1/3

Outil valgrind.

Exemple de vérification d’initialisation de variable :

rex@monet:/tmp/Debug$ valgrind ./segfault 
==8756== Memcheck, a memory error detector
==8756== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==8756== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==8756== Command: ./segfault
==8756== 
==8756== Use of uninitialised value of size 4
==8756==    at 0x804840A: main (segfault.c:6)
...

Exemple de vérification de débordement de blocs alloués :

$ cat -b debordement.c
     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 #define MAX_ALLOC 10
     4 int main(void){
     5 char *tab=malloc(MAX_ALLOC*sizeof(char));
     6 int i;
     7 for(i=1;i<=MAX_ALLOC;i++) tab[i]=i;
     8 for(i=1;i<=MAX_ALLOC;i++) printf("%d\n",tab[i]);
     9 return 0;
    10 }
$ valgrind ./debordement
==5345== Memcheck, a memory error detector
...
==5345== Invalid write of size 1
==5345==    at 0x804847D: main (debordement.c:7)
==5345==  Address 0x41a8032 is 0 bytes after a block of size 10 alloc'd
==5345==    at 0x4028308: malloc (vg_replace_malloc.c:263)
==5345==    by 0x8048460: main (debordement.c:5)
...

4.11 Vérificateur mémoire 2/3

Vérification de fuite mémoire :

$ cat -b allocfree.c
     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 #define NB_CHAINES 10
     4 #define MAX_CHAINE 1024
     5 int main(void){
     6 char **tab=malloc(NB_CHAINES*sizeof(char *));
     7 int i;
     8 for(i=0;i<NB_CHAINES;i++){
     9   tab[i]=malloc(MAX_CHAINE*sizeof(char));
    10   sprintf(tab[i],"%d",i);
    11   }
    12 for(i=0;i<NB_CHAINES;i++)
    13   printf("%s\n",tab[i]);
    14 return 0;
$ valgrind --leak-check=full ./allocfree
==5405== Memcheck, a memory error detector
...
==5405== HEAP SUMMARY:
==5405==     in use at exit: 10,280 bytes in 11 blocks
==5405==   total heap usage: 11 allocs, 0 frees, 10,280 bytes allocated
==5405== 
==5405== 10,280 (40 direct, 10,240 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==5405==    at 0x4028308: malloc (vg_replace_malloc.c:263)
==5405==    by 0x8048491: main (allocfree.c:6)
==5405== 
==5405== LEAK SUMMARY:
==5405==    definitely lost: 40 bytes in 1 blocks
==5405==    indirectly lost: 10,240 bytes in 10 blocks
==5405==      possibly lost: 0 bytes in 0 blocks
==5405==    still reachable: 0 bytes in 0 blocks
==5405==         suppressed: 0 bytes in 0 blocks
...

Exercice "réparer la fuite mémoire" :
- ajouter les free nécessaires ;
- vérifiez avec valgrind que la fuite est réparée.

Vérification des doubles libérations :

$ cat -b doublefree.c
     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 int main(void){
     4 int *x=malloc(sizeof(int));
     5 int *y=x;
     6 *x=3;
     7 printf("x=%d y=%d\n",*x,*y);
     8 free(x);
     9 free(y);
    10 return 0;
    11 }
$ valgrind ./doublefree
==3889== Memcheck, a memory error detector
...
==3889== Invalid free() / delete / delete[] / realloc()
==3889==    at 0x402750C: free (vg_replace_malloc.c:427)
==3889==    by 0x80484DE: main (doublefree.c:9)
==3889==  Address 0x41a8028 is 0 bytes inside a block of size 4 free'd
==3889==    at 0x402750C: free (vg_replace_malloc.c:427)
==3889==    by 0x80484D2: main (doublefree.c:8)
...

4.12 Vérificateur mémoire 3/3

Pas de vérification des bornes de tableaux statiques :

$ cat -b bornes.c
     1 #include <stdio.h>
     2 int main(void){
     3 char tab[10];
     4 int i;
     5 for(i=1;i<=10;i++) tab[i]=i;
     6 for(i=1;i<=10;i++) printf("%d\n",tab[i]);
     7 return 0;
     8 }
$ valgrind ./bornes
==5277== Memcheck, a memory error detector
...
==5277== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 6)

4.13 Outils divers 1/4

Outil strace : system trace.

Exemple d’utilisation sur un programme bien connu :

$ strace ./embryon > /dev/null
execve("./embryon", ["./embryon"], [/* 29 vars */]) = 0
write(1, "Bonjour !\n\0", 11)           = 11
_exit(0)

Exemple d’utilisation avec suivi des fils :

$ strace -f bash
...
getgid32()                              = 1000
access("/bin/cat", R_OK)                = 0
rt_sigprocmask(SIG_BLOCK, [INT CHLD], [], 8) = 0
pipe([3, 4])                            = 0
clone( child_stack=0, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0xb7594728) = 4724
Process 4724 attached
[pid  4723] setpgid(4724, 4724)         = 0
[pid  4723] rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
[pid  4724] rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
[pid  4723] rt_sigprocmask(SIG_BLOCK, [CHLD], [], 8) = 0
...
[pid  4724] execve("/bin/cat", ["cat", "/etc/hosts"], [/* 28 vars */]) = 0
...
[pid  4724] open("/etc/hosts", O_RDONLY|O_LARGEFILE) = 3

Exercice "manipulation de strace":
- utilisez strace pour trouver :
  - les fichiers d’initialisation de nano ;
  - les fichiers d’initialisation de vim.

4.14 Outils divers 2/4

Outil lsof : list open files.

Exemples d’utilisation

# lsof +c15 +D /var/log
COMMAND          PID USER   FD   TYPE DEVICE SIZE/OFF   NODE NAME
rsyslogd        2332 root    1w   REG   8,17   379544 131088 /var/log/syslog
rsyslogd        2332 root    2w   REG   8,17   144756 132190 /var/log/kern.log
rsyslogd        2332 root    5w   REG   8,17    98952 132213 /var/log/messages
rsyslogd        2332 root    6w   REG   8,17    49862 132212 /var/log/debug
rsyslogd        2332 root    7w   REG   8,17   231211 132189 /var/log/daemon.log
rsyslogd        2332 root    8w   REG   8,17      256 132200 /var/log/lpr.log
rsyslogd        2332 root    9w   REG   8,17    21817 132191 /var/log/auth.log
rsyslogd        2332 root   10w   REG   8,17      388 132195 /var/log/user.log
gdm-simple-slav 2629 root    1u   REG   8,17      499 131102 /var/log/gdm3/:0-slave.log
gdm-simple-slav 2629 root    2u   REG   8,17      499 131102 /var/log/gdm3/:0-slave.log
Xorg            2660 root    0r   REG   8,17    29683 131105 /var/log/Xorg.0.log
Xorg            2660 root    2w   REG   8,17    20553 131127 /var/log/gdm3/:0.log
cupsd           2909 root    4u   REG   8,17      641 131538 /var/log/cups/access_log
cupsd           2909 root    5u   REG   8,17      742 131677 /var/log/cups/error_log
cupsd           2909 root    6u   REG   8,17        0 131111 /var/log/cups/page_log
console-kit-dae 3299 root    8w   REG   8,17    11983 131108 /var/log/ConsoleKit/history
gdm-session-wor 3556 root    1w   REG   8,17      499 131102 /var/log/gdm3/:0-slave.log
gdm-session-wor 3556 root    2w   REG   8,17      499 131102 /var/log/gdm3/:0-slave.log

$ tty
/dev/pts/0
$ lsof /dev/pts/0
COMMAND    PID  USER   FD   TYPE DEVICE SIZE/OFF NODE NAME
gnome-ter 3705 pifou   17w   CHR  136,0      0t0    3 /dev/pts/0
bash      3818 pifou    0r   CHR  136,0      0t0    3 /dev/pts/0
bash      3818 pifou    1u   CHR  136,0      0t0    3 /dev/pts/0
bash      3818 pifou    2u   CHR  136,0      0t0    3 /dev/pts/0
bash      3818 pifou  255u   CHR  136,0      0t0    3 /dev/pts/0
lsof      4026 pifou    0u   CHR  136,0      0t0    3 /dev/pts/0
lsof      4026 pifou    1u   CHR  136,0      0t0    3 /dev/pts/0
lsof      4026 pifou    2u   CHR  136,0      0t0    3 /dev/pts/0

# lsof /tmp/.X11-unix/X0 
COMMAND  PID USER   FD   TYPE     DEVICE SIZE/OFF NODE NAME
Xorg    2660 root    3u  unix 0xf7335940      0t0 6763 /tmp/.X11-unix/X0

4.15 Outils divers 3/4

Lancement sur processus actifs :

$ ./repeter &
[1] 4099
Bonjour
$ gdb
GNU gdb (GDB) 7.4.1-debian
Copyright (C) 2012 Free Software Foundation, Inc.
...
(gdb) attach 4099
Attaching to process 4099
...
0xb77cd424 in __kernel_vsyscall ()
(gdb) list
1 #include <stdio.h>
2 #include <unistd.h>
3 int main(void){
4 while(1){ sleep(5); printf("Bonjour\n"); }
5 return 0;
6 }
(gdb) where
#0  0xb77cd424 in __kernel_vsyscall ()
#1  0xb76f5300 in __nanosleep_nocancel () at ../sysdeps/unix/syscall-template.S:82
#2  0xb76f5150 in __sleep (seconds=0) at ../sysdeps/unix/sysv/linux/sleep.c:138
#3  0x08048461 in main () at repeter.c:4
(gdb) break 4
Breakpoint 1 at 0x8048455: file repeter.c, line 4.
(gdb) c
Continuing.
Bonjour

Breakpoint 1, main () at repeter.c:4
4 while(1){ sleep(5); printf("Bonjour\n"); }
(gdb) c
Continuing.
Bonjour

Breakpoint 1, main () at repeter.c:4
4 while(1){ sleep(5); printf("Bonjour\n"); }
(gdb) detach
Detaching from program: ./repeter, process 4099
(gdb) quit

$ pidof repeter
4099
$ lsof -p 4099
COMMAND  PID  USER   FD   TYPE DEVICE SIZE/OFF   NODE NAME
repeter 4099 pifou  cwd    DIR   8,17     4096 414993 /home/pifou/Exercices/Debug
repeter 4099 pifou  rtd    DIR   8,17     4096      2 /
repeter 4099 pifou  txt    REG   8,17     5888 399080 /home/pifou/Exercices/Debug/repeter
repeter 4099 pifou  mem    REG   8,17  1437864 524645 /lib/i386-linux-gnu/i686/cmov/libc-2.13.so
repeter 4099 pifou  mem    REG   8,17   117960 525200 /lib/i386-linux-gnu/ld-2.13.so
repeter 4099 pifou    0u   CHR  136,0      0t0      3 /dev/pts/0
repeter 4099 pifou    1u   CHR  136,0      0t0      3 /dev/pts/0
repeter 4099 pifou    2u   CHR  136,0      0t0      3 /dev/pts/0

$ strace -p 4099
Process 4099 attached - interrupt to quit
restart_syscall(<... resuming interrupted call ...>) = 0
write(1, "Bonjour\n", 8) = 8
rt_sigprocmask(SIG_BLOCK, [CHLD], [], 8) = 0
rt_sigaction(SIGCHLD, NULL, {SIG_DFL, [], 0}, 8) = 0
rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
nanosleep({5, 0}, 0xbfa2bdc4)           = 0

4.16 Outils divers 4/4

Exercice "Ouverture de fichiers en boucle" :
- créez un répertoire Outils ;
- écrivez un programme effectuant en boucle :
  - l’ouverture d’un fichier de nom fichier_XX ;
  - l’écriture du numéro XX dans le fichier ;
  - une attente de 100ms avec usleep.
- trouvez le maximum de descripteurs avec strace ;
- verifiez la cohérence avec ulimit ;
- corrigez le programme pour ne pas dépasser le maximum ;
- suivez la progression du programme avec lsof.

5 Structures de données

5.1 Structures cartésiennes 1/3

Structures struct

un exemple vaut mieux qu’un long discours :

struct personne_s {
  char nom[MAX_NOM];
  char prenom[MAX_NOM];
  int age;
  long long noss;
  };

même exemple avec une définition de type :

typedef struct {
  char nom[MAX_NOM];
  char prenom[MAX_NOM];
  int age;
  long long noss;
  } personne_t;

l’initialisation peut se faire en séquence :

struct personne_s moi={"REDON","Xavier",45,1681086424242};
personne_t encore=moi;

l’initialisation peut se faire en désordre :

struct personne_s moi={.noss=1681086424242,.nom="REDON"};
personne_t encore=moi;

la copie de structure est possible ;

l’accès est possible via l’opérateur . :

struct personne_s moi;
bzero(&moi,sizeof moi);
strcpy(moi.nom,"REDON");
moi.noss=1681086424242;

l’accès est possible via l’opérateur -> :

struct personne_s *moi=calloc(1,sizeof moi);
strcpy(moi->nom,"REDON"); // equivalent strcpy((*moi).nom,"REDON");
moi->noss=1681086424242;  // equivalent (*moi).noss=1681086424242;

5.2 Structures cartésiennes 2/3

Champs bits

exemple d’utilisation (non standard) :

typedef struct {
  unsigned char chiffre_dizaine : 4;
  unsigned char chiffre_unite : 4;
  } octet_t;

ordre de stockage non standardisé ;

il vaut mieux utiliser des masques :

#define CHIFFRE_DIZAINE(octet)  (((octet)>>4)&0x0f)
#define CHIFFRE_UNITE(octet)  ((octet)&0x0f)

Unions union
- chaque champ se trouve à la même adresse ;
- un exemple vaut mieux qu’un long discours :
```
struct figure_s {
  enum { point,cercle,rectangle } type;
  int x,y;
  union {
    struct { int r ; } cercle;
    struct { int l,h ; } rectangle;
    } specifique;
  };
```
- l’alignement peut être maîtrisé :
```
#pragma pack(1)
...
#pragma pack()
```
- exercice : affichez la taille de la structure figure_s ...
- ... sans directive d’alignement et alignée sur octets.

5.3 Structures cartésiennes 3/3

Exercice "Arduino, LED et boutons" :
- vous utiliserez un Arduino Uno avec 14 E/S numériques ;
- les broches E/S numérotées de 0 à 7 sont sur le port D ;
- les broches E/S numérotées de 8 à 13 sont sur le port B ;
- le sens des E/S se spécifie par les registres DDRD et DDRB ;
- sur les registres DDRx, un 1 correspond à une sortie, un 0 à une entrée ;
- la lecture des entrées se fait sur les registres PIND et PINB ;
- l’activation des sorties se fait par les registres PORTD et PORTB ;
- pour activer les résistances de rappel, utilisez les registres PORTx ;
- un exemple de programme pour allumer 4 LED quand un bouton est appuyé :
```
#include <avr/io.h>             // for the input/output register
#include <util/delay.h>         // for _delay_ms function
int main(void){
DDRB |= 0x0f;                   // pins 8 to 11 as outputs
DDRD &= 0x83;                   // pins 2 to 6 as inputs
PORTD |= 0x7c;                  // pull-up activated on pins 2 to 6
while(1){
  if((PIND&0x7c)==0x7c) PORTB=0x00; else PORTB=0x0f;
  _delay_ms(50);
  }
}
```
- pour compiler et charger le programme utilisez les commandes :
```
avr-gcc -Wall -mmcu=atmega328p -DF_CPU=16000000 -Os test.c -o test
avr-objcopy -j .text -j .data -O ihex test test.hex
avrdude -F -v -p atmega328p -c stk500v1 -b 115200 -P /dev/ttyACM0 -U flash:w:test.hex
```
- utilisez des structures champs bits pour représenter LED et boutons ;
- réalisez un chenillard sur les LED puis une interface boutons/LED ;
- écrivez des programmes plus compacts en utilisant ...
- ... les opérateurs sur les bits >>, & et |.
Exercice "interrogation d’un serveur DNS" :
- dérivez de la RFC 1035 la structure des messages DNS ;
- examinez particulièrement les sections 4 et 3.2 ;
- définissez la structure d’une question DNS ;
- remplissez la structure avec les paramètres ;
- définissez la structure d’une réponse DNS ;
- analysez la structure réponse ...
- ... affichez la de façon lisible pour un humain ;
- pour tester utilisez la commande :
```
question www.polytech-lille.fr | nc -u beuvry.escaut.net 53 | reponse
```

5.4 Listes contigües 1/2

Structure de données Collection.

Implantation statique en C :

typedef struct {
  element_t contenu[MAX_ELEMENTS];
  int nombre;
  } liste_t;
liste_t liste={{},0};

Implantation dynamique en C :

typedef struct {
  element_t *contenu;
  int nombre;
  int alloue;
  } liste_t;
liste_t liste={NULL,0,0};

Opérations sur les listes contigües
- accès, direct O(1) ;
- recherche :
  - sur liste non ordonnée, séquentielle O(n) ;
  - sur liste ordonnée, dichotomie O(log₂(n)).
- ajout :
  - sur liste non ordonnée, direct O(1) ;
  - sur liste ordonnée, insertion O(n) ;
  - implantation dynamique, éventuelle ré-allocation.
- suppression :
  - sur liste non ordonnée, échange O(1) ;
  - sur liste ordonnée, décalage O(n) ;
  - implantation dynamique, éventuelle dé-allocation.
Exercice "Bibliothèque liste contigüe ordonnée" :
- créez un répertoire Structures ;
- créez un sous-répertoire ListeContigue ;
- écrivez le fichier de configuration makefile ;
- implantez les fonctions recherche et ajout ;
- écrivez dans un sous-répertoire TriParListe ...
- ... un programme de tri de nombres via votre bibliothèque.

5.5 Listes contigües 2/2

Une liste contigüe permet d’implanter files et piles.
Implantation d’une file :
- ajout en début de liste, suppression en fin de liste ;
- opérations enfiler, défiler, premier, taille ;
- implantation peu efficace (enfiler).
Exercice "jeu classique Centipède" :
- créez un répertoire Projets/Centipede ;
- créez deux sous-répertoires File et Parcourir ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique GraphiqueJeux.tgz ;
- implantez la bibliothèque de file à base de liste contigüe dynamique ;
- réalisez le programme principal :
  - définissez une liste contigüe pour stocker les positions des champignons ;
  - chargez les lutins du mille-pattes et du champignon ;
  - écrivez une fonction pour obtenir des positions aléatoires pour les champignons ;
  - écrivez une fonction pour effacer l’écran et afficher les champignons ;
  - placez le mille-pattes au hasard mais en évitant qu’il sorte immédiatement du plateau ;
  - définissez une file de positions pour représenter le mille-pattes ;
  - enfilez la position initiale de la tête du mille-pattes dans la file ;
  - écrivez la boucle de gestion du mille-pattes :
    - si le mille-patte ne s’étire pas défilez son dernier segment et effacez le ;
    - remplacez l’ancienne tête du mille-patte par le segment de corps adapté ;
    - enfilez la nouvelle position de la tête du mille-patte et affichez la ;
    - suivant les touches pressées, calculez la nouvelle position du mille-pattes ;
    - vérifiez, par la couleur, si la nouvelle case est vide ou non :
      - case vide : rien de particulier à faire ;
      - case avec champignon : incrémenter la longueur du mille-patte ;
      - autre case non vide : le mille-patte est mort ;
      - case hors tableau : le mille-patte est mort.
  - n’oubliez pas de mettre la surface graphique à jour ;
  - si le dernier champignon est boulotté passez au niveau suivant ;
  - quand le mille-pattes meurt mettez à jour le fichier des scores :
    - le score du joueur correspond au nombre de champignons avalés ;
    - la structure des scores comprend un pseudo et le nombre ;
    - les structures des scores sont stockés dans un fichier binaire ;
    - demandez au joueur sont pseudo et cherchez le dans le fichier ;
    - s’il existe modifiez la structure déjà écrite dans le fichier ;
    - s’il n’existe pas ajoutez une structure dans le fichier binaire ;
    - affichez, dans l’ordre, les dix premiers scores avec les pseudos.
Implantation d’une pile :
- ajout en fin de liste, suppression en fin de liste ;
- opérations empiler, dépiler, sommet, taille ;
- implantation efficace (temps constant).
Exercice "aider la souris à sortir du labyrinthe" :
- créez un répertoire Projets/Souris ;
- créez deux sous-répertoires Pile et Parcourir ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique Graphique.tgz ;
- implantez la bibliothèque de pile à base de liste contigüe dynamique ;
- réalisez le programme principal :
  - chargez l’image du labyrinthe avec la bibliothèque fournie ;
  - appliquez l’algorithme de la main gauche (garder un mur à gauche) ;
  - il est conseillé de créer une structure pour stocker la position ;
  - marquez votre passage en changeant la couleur du sol ;
  - empilez les cellules visitées ;
  - si vous repassez sur une cellule déjà visitée ...
  - dépilez les cellules jusqu’à trouver la cellule courante ;
  - arrivé à la sortie, affichez le chemin direct.

5.6 Listes chaînées 1/2

Implantation en C :

typedef struct cellule_s {
  element_t contenu;
  struct cellule_s *suivant;
  } liste_t;
liste_t *liste=NULL;

Opérations sur les listes chaînées
- accès et recherche, séquentiel O(n) ;
- ajout :
  - sur liste non ordonnée, ajout en tête, direct O(1) ;
  - sur liste ordonnée, recherche puis ajout, séquentiel O(n).
- suppression, séquentiel O(1) (si pointeur sur précédent).
Exercice "Bibliothèque liste chainée" :
- créez un sous-répertoire Structures/ListeChainee ;
- écrivez le fichier de configuration makefile ;
- implantez les fonctions recherche, ajout et suppression ;
- écrivez dans un sous-répertoire Allocation un programme :
  - qui analyse des ordres comme alloc 50 ou free 1 ;
  - un ordre alloc n simule l’allocation de n octets ;
  - un ordre free i simule la libération du bloc de rang i ;
  - représentez les blocs libres et alloués par une unique liste chaînée ;
  - affichez l’état des blocs après chaque ordre ;
  - deux blocs de même type doivent être fusionnés.

5.7 Listes chaînées 2/2

Une liste chaînée permet d’implanter files et piles.
Implantation d’une file :
- ajout en queue de liste, suppression en tête de liste ;
- opérations enfiler, défiler, premier ;
- implantation efficace avec un pointeur de queue.
Implantation d’une pile :
- ajout en tête de liste, suppression en tête de liste ;
- opérations empiler, dépiler, sommet, taille ;
- implantation efficace (temps constant).
Exercice "jeu classique Centipede" :
- reprenez votre programme implanté avec des listes contigües ;
- implantez la file en utilisant des listes chaînées.
Exercice "jeu classique Invaders" :
- créez un répertoire Projets/Invaders ;
- créez deux sous-répertoires ListeChainee et Invaders ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique GraphiqueJeux.tgz ;
- implantez la bibliothèque de liste chaînée ;
- réalisez le programme principal :
  - créez des structures pour représenter monstres, bombes et missiles ;
  - les structures comprennent la position et l’état des objets ;
  - créez trois listes chainées pour les monstres, les bombes et les missiles ;
  - écrivez une fonction pour initialiser la liste monstres suivant le niveau ;
  - écrivez une fonction pour faire déplacer les monstres ...
  - ... cette fonction indique si un monstre est arrivé au sol ;
  - écrivez une fonction de lancement aléatoire de bombe ;
  - écrivez une fonction de gestion des bombes :
    - la fonction gère la trajectoire des bombes ;
    - les bombes sortant de l’écran sont supprimées de la liste ;
    - la fonction indique en retour si le canon a été touché.
  - écrivez une fonction de gestion des missiles :
    - la fonction gère la trajectoire des missiles ;
    - les missiles sortant de l’écran sont supprimées de la liste ;
    - la collision avec tous les monstres est testée ;
    - une collision entraine la suppression du missile et du monstre ;
    - la fonction indique en retour s’il ne reste plus aucun monstre.
  - écrivez la fonction principale :
    - le canon est déplacé suivant les touches pressées ;
    - le cas échéant un missile est ajouté dans la liste correspondante ;
    - appel de la fonction de déplacement des monstres ;
    - appels des fonctions de gestion des missiles et des bombes ;
    - si le canon est détruit par les monstres ou une bombe arrêter le jeu ;
    - s’il ne reste plus de monstre, il y a changement de niveau ;
    - la surface est intégralement re-dessinée à chaque itération.
Exercice "génération de labyrinthe" :
- créez un répertoire Projets/Labyrinthe ;
- créez deux sous-répertoires ListeChainee et Construire ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique Graphique.tgz ;
- implantez la bibliothèque de liste chaînée ;
- réalisez le programme principal :
  - utilisez la bibliothèque fournie pour réaliser l’affichage ;
  - tracez le sol en blanc, laissez les murs en noir ;
  - utilisez l’algorithme aléatoire de Prim :
    - considère l’image découpée en pavés en 8x8 pixels ;
    - les pavés du bord de l’image sont des murs non destructibles ;
    - les pavés de coordonnées toutes deux paires sont des chemins ;
    - les autres pavés sont des murs destructibles ;
    - choisissez comme départ un pavé de type chemin en seconde colonne ;
    - ajoutez ce pavé dans la liste chaînée des chemins à traiter ;
    - tirez un chemin dans la liste chaînée au hasard (fonction rand) ;
    - détruisez un mur entre ce chemin et un autre chemin déjà traité ;
    - ajoutez à la liste des chemins, les chemins adjacents non encore visités ;
    - recommencez jusqu’à ce que la liste des chemins soit vide.
  - n’oubliez pas de sauvegarder votre labyrinthe pour la souris.
Exercice "génération de courbes 3D paramétriques en STL" :
- le programme prend un argument : le nom des fichiers résultats ;
- deux fichiers sont produits : un fichier STL ASCII .ast et un fichier STL binaire .stl ;
- les courbes 3D sont définies dans un tableau de structures dans le fichier courbes.c :
```
struct fonction_s {
  float (*x)(float);
  float (*y)(float);
  float (*z)(float);
  float t_min;
  float t_max;
  float t_pas;
  float taille;
  }
```
- les courbes sont pixélisées avec des cubes identiques d’arêtes parallèles aux axes ;
- les cubes des courbes sont accumulés dans une liste chaînée ;
- créez un répertoire pour votre projet, par exemple Courbes3D ;
- votre projet comporte des sous-répertoires :
  - Liste, contient la bibliothèque de gestion de liste chaînée ;
  - Geometrie, contient la bibliothèque des opérations 3D sur les cubes ;
  - STL, contient la bibliothèque de convertion des cubes en format STL ;
  - Courbes, contient l’exécutable utilisant les bibliothèques.
- écrivez les cinq fichiers de compilation automatique Makefile ;
- l’incrémentation du paramétre entre deux cubes peut se faire par dichotomie :
  - les valeurs minimale et maximum du paramètre sont précisés dans la structure de la fonction ;
  - le pas d’incrémentation de base est précisé dans la structure de la fonction ;
  - la distance entre deux cubes est définie comme le minimum des distances sur les trois axes ;
  - le pas réel est trouvé par dichotomie entre le pas de base et 0 avec la distance comme critère.
- Les courbes ne doivent pas comprendre de cubes en collision :
  - à chaque ajout de cube dans la liste, vérifier la collision avec tous les autres ;
  - retirer tous les cubes en collision, les mettre dans une liste de collision ;
  - scinder chaque cube dans la liste de collision en 8 sous-cubes ;
  - procéder avec les sous-cubes comme avec les nouveaux cubes ;
  - si la nouvelle liste de collision est non vide, scinder à nouveau les sous-cubes ;
  - ne pas scinder des sous-cubes en collision de taille trop faible : les détruire.
- Trouvez un ensemble de courbes paramétrique esthétique et imprimable par une imprimante 3D.

5.8 Généralisation des listes chaînées

Listes doublement chaînées, implantation en C :

typedef struct cellule_s {
  element_t contenu;
  struct cellule_s *suivant;
  struct cellule_s *precedent;
  } liste_t;
liste_t *liste=NULL;

Arbres binaires, implantation en C :

typedef struct noeud_s {
  element_t contenu;
  struct noeud_s *droit;
  struct noeud_s *gauche;
  } arbre_t;
arbre_t *arbre=NULL;

Exercice "calcul d’expression préfixée" :
- créez un sous répertoire Structures/Prefixe ;
- le programme lit des entiers et les opérations +, -, / et * ;
- l’expression est stockée sous la forme d’un arbre binaire ;
- l’expression est évaluée à l’aide d’une fonction récursive.

Graphes, implantation en C :

typedef struct noeud_s {
  element_t contenu;
  struct noeud_s **noeuds;
  } graphe_t;
graphe_t *graphe=NULL;

Exercice "visualisation du graphe AST de gcc" :
- reprise de votre travail d’analyse de l’AST ;
- utilisation de la bibliothèque igraph ;
- génération du graphe au format graphviz.
Exercice "compression de Huffman" ?

Ce document a été traduit de L^AT_EX par H^EV^EA