Récemment, je suis tombé sur cette série d’articles d’Eli Bendersky sur la compilation à la volée (JIT compilation : Just-In-Time compilation) :

• Adventures in JIT compilation: Part 1 - an interpreter
• Adventures in JIT compilation: Part 2 - an x64 JIT
• Adventures in JIT compilation: Part 3 - LLVM
• Adventures in JIT compilation: Part 4 - in Python

Eli utilise le C++ pour les trois premières parties, mais dans la quatrième il montre comment faire de la compilation à la volée en Python.

En lisant ça, je me suis demandé « Comment faire l’équivalent en Ruby ? ». Et bien c’est ce que nous allons voir !

Pour des raisons de simplicité et concision, les exemples de codes de cet article ne sont pas portable (limité à Linux/x86_64). Cependant, la démarche présentée est applicable sur d’autres OS/architecture.

Comment exécuter du code compilé à la volée en Ruby

Les étapes pour exécuter du code compilé à la volée sont les suivantes :

1. Allouer de la mémoire pour y placer le code à exécuter.
2. Créer une fonction à partir de l’adresse de la zone mémoire contenant le code.
3. Utiliser la fonction autant que l’on veut.
4. Libérer la mémoire utilisée.

Étant donné que nous allons devoir faire de la programmation relativement bas niveau (allocation mémoire entre autre), nous allons nous reposer sur l’excellent module ffi (dont j’ai déjà eu l’occasion de parler ici).

En première approche pour l’étape 1 on pourrait penser à FFI::MemoryPointer.new mais il y a de très fortes chances pour que cela se termine en Segmentation Fault (ou équivalent).

En effet, pour des raisons de sécurité, la mémoire est généralement allouée soit en « lecture/écriture » (RW : read/write), soit en « lecture/exécution » (RX : read/execute)¹. Et comme, de manière générale, les fonctions d’allocation (malloc & cie en C, FFI::MemoryPointer.new en Ruby, …) renvoient de la mémoire RW nous ne pourrons pas les utiliser pour allouer la mémoire où nous allons placer notre code.

Heureusement, il existe un appel système qui nous permet de spécifier les droits d’une zone mémoire lors de son allocation : mmap. Cette fonction est extrêmement pratique et a de nombreux cas d’usages, mais dans le cas présent nous allons en avoir une utilisation assez simple :

1. Allouer via mmap une zone mémoire de taille suffisante pour recevoir le code (cette zone sera allouée en RW).
2. Stocker le code dans cette zone mémoire.
3. Changer les permissions de la zone mémoire via mprotect pour la passer en RX.

Nous pourrions directement allouer la mémoire en RWX (et ainsi éviter d’avoir à appeler mprotect) mais ce n’est pas une bonne pratique (du point de vue sécurité) d’avoir les droits en écriture ET en exécution en même temps sur une même zone mémoire.

Wrapper mmap pour Ruby

Étant donné que mmap & cie ne sont pas disponibles de base en Ruby, contrairement à Python, nous allons faire un petit wrapper nous-même². Ce wrapper ne sera pas exposé publiquement, c’est un détail d’implémentation, et sera manipulé via une classe qui représente une fonction compilée à la volée : JitFunction.

Mais d’abord, voyons le wrapper en question.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

require 'ffi'

class JitFunction

  […]

  module Internal
    extend FFI::Library
    ffi_lib FFI::Library::LIBC

    attach_function 'mmap',     %i[pointer size_t int int int off_t], :pointer
    attach_function 'mprotect', %i[pointer size_t int], :int
    attach_function 'munmap',   %i[pointer size_t], :int

    PROT_NONE  = 0x0 # Data cannot be accessed.
    PROT_READ  = 0x1 # Data can be read.
    PROT_WRITE = 0x2 # Data can be written.
    PROT_EXEC  = 0x4 # Data can be executed.

    PROT_RW = PROT_READ | PROT_WRITE
    PROT_RX = PROT_READ | PROT_EXEC

    MAP_SHARED    = 0x1   # Share changes.
    MAP_PRIVATE   = 0x2   # Changes are private.
    MAP_ANONYMOUS = 0x20  # Don't use a file.

    MAP_FAILED = FFI::Pointer.new(:void, -1)
  end
  private_constant :Internal
end

Rien de bien compliqué : on déclare les trois fonctions que nous allons utiliser (mmap pour allouer la mémoire, mprotect pour changer les permissions et munmap pour libérer la mémoire) et les constantes dont nous allons avoir besoin (il existe d’autres constantes, vous pouvez consulter man 2 mmap pour la liste complète).

Attention : ce wrapper n’est pas portable (il ne fonctionnera pas pour Windows, sur d’autres UNIX les valeurs des constantes peuvent être différentes, …).

La classe JitFunction

Voyons maintenant la classe qui va nous permettre de créer et d’exécuter des fonctions compilées à la volée.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

require 'ffi'

class JitFunction
  def initialize(ret, args, code)
    @size = code.bytesize
    @address = Internal.mmap(nil, @size, Internal::PROT_RW,
                             Internal::MAP_PRIVATE | Internal::MAP_ANONYMOUS,
                             -1, 0)
    raise 'cannot map memory' if @address == Internal::MAP_FAILED
    @address.put_string(0, code)
    status = Internal.mprotect(@address, @size, Internal::PROT_RX)
    raise "cannot change memory's permission" if status == -1
    @func = FFI::Function.new(ret, args, @address, convention: :default)
  end

  def call(*args)
    @func.call(*args)
  end

  def free
    Internal.munmap(@address, @size)
  end

  module Internal
    […]
  end
  private_constant :Internal
end

On peut voir que l’interface de la classe est composée de trois méthodes publiques :

• initialize qui prend en argument le code de la fonction et qui crée un objet FFI::Function.
• call qui permet d’exécuter la fonction.
• free qui libère la mémoire utilisée par le code de la fonction.

Il n’y a pas grand chose à dire sur call (un simple wrapper autour de la méthode call de l’objet FFI::Function) ou free (un simple wrapper autour de munmap).

En revanche, initialize mérite que l’on s’y attarde.

• La ligne 5 récupère la taille, en octet, du code de la fonction.
• La ligne 6 alloue la mémoire pour le code via mmap. On remarque que la mémoire est alloué en RW (comme l’indique le paramètre PROT_RW). La mémoire allouée n’est pas accessible aux autres processus (utilisation de MAP_PRIVATE au lieu de MAP_SHARED) et n’est pas liée à un fichier sur le disque (utilisation de MAP_ANONYMOUS).
• La ligne 9 lève une exception si l’allocation a échouée (Attention : en cas d’erreur mmap ne renvoie pas NULL mais une valeur bien spécifique représentée par MAP_FAILED³).
• La ligne 10 copie le code de la fonction dans la zone allouée.
• Étant donné que nous n’allons plus modifier la mémoire, la ligne 11 change les permissions de la zone mémoire de RW en RX et la ligne 12 lève une exception en cas d’échec.
• Finalement, la ligne 13 crée un objet FFI::Function en précisant le type de retour, le type des arguments et l’adresse du code à exécuter.

Test

Nous pouvons maintenant tester la classe JitFunction en reprenant l’exemple utilisé par Eli dans son quatrième article : une fonction qui ajoute 4 à un entier passé en argument et retourne le résultat.

1
2
3
4
5
6
7
8
9

if __FILE__ == $PROGRAM_NAME
  code = "\x48\x89\xf8\x48\x83\xc0\x04\xc3"
  func = JitFunction.new(:long, [:long], code)
  begin
    puts func.call(-100)
  ensure
    func.free
  end
end

Lorsque l’on exécute ce script, -96 s’affiche. Ça fonctionne \o/

Le code complet de jit.rb est disponible ici.

Exemple d’utilisation : Brainfuck

Afin de montrer un exemple d’utilisation « réel » de la classe JitFunction, nous allons développer un programme qui va compiler à la volée un programme Brainfuck en assembleur x86_64 pour Linux puis l’exécuter : bf-jit.rb.

Point d’entrée

Commençons par le commencement : la fonction main.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

require 'set'

# Brainfuck's instruction set.
INSTRUCTION_SET = Set.new('[]><+-.,'.chars).freeze

if __FILE__ == $PROGRAM_NAME
  abort 'Missing argument: expected filename' if ARGV.empty?
  bf_code = File.read(ARGV[0]).chars.select! { |c| INSTRUCTION_SET.include? c }
  memory  = FFI::MemoryPointer.new(:uchar, 30_000)
  bf_prog = JitFunction.new(:void, [], compile_bf(bf_code, memory))
  begin
    bf_prog.call
  ensure
    bf_prog.free
    memory.free
  end
end

• La ligne 7 vérifie que le script est bien appelé avec un argument (le nom du fichier source Brainfuck).
• La ligne 8 lit le contenu du fichier et ne garde que les caractères qui font partie du jeu d’instructions Brainfuck.
• La ligne 9 alloue la mémoire pour l’exécution du programme (pour rappel, un programme Brainfuck s’attend à avoir au moins 30 000 octets de mémoire à disposition).
• La ligne 10 compile le code source et crée un objet JitFunction. Étant donné que le programme Brainfuck s’exécute sans interaction avec le reste du script on le représente par une fonction sans argument et avec un type de retour void.
• Finalement, la ligne 12 exécute la fonction et les lignes 14 et 15 libèrent la mémoire allouée.

La compilation

Pour rappel, les instructions du Brainfuck sont les suivantes :

• > : déplace le pointeur d’une case mémoire vers la droite ;
• < : déplace le pointeur d’une case mémoire vers la gauche ;
• + : incrémente la valeur stockée dans la case mémoire actuellement pointée ;
• - : décrémente la valeur stockée dans la case mémoire actuellement pointée ;
• . : affiche le caractère ASCII correspondant à la valeur de la case mémoire actuellement pointée ;
• , : stocke la valeur ASCII du caractère lu dans la case mémoire actuellement pointée ;
• [ : saute à l’instruction suivant le ] correspondant si la valeur de la case mémoire actuellement pointée est égale à zéro ;
• ] : saute à l’instruction suivant le [ correspondant si la valeur de la case mémoire actuellement pointée est différente de zéro.

On voit que pour interpréter du code Brainfuck nous allons avoir besoin de deux pointeurs :

1. un pointeur sur la mémoire : c’est le pointeur utilisé par la plupart des instructions (toutes sauf [ et ]).
2. un pointeur sur le code : c’est le pointeur qui permet de savoir quelle est la prochaine instruction à exécuter (il est incrémenté automatiquement après chaque instruction, sauf pour les instructions [ et ] qui peuvent le modifier de manière conditionnelle).

Dans le cadre d’un interpréteur, nous devons gérer ces deux pointeurs nous-même. En revanche, dans le cas de la compilation à la volée, nous allons générer du code machine et c’est le processeur qui va s’occuper de savoir quelle est la prochaine instruction à exécuter : nous avons seulement besoin de gérer le pointeur sur la mémoire. Pour représenter ce pointeur nous allons utiliser un registre. Cependant, on ne peut pas utiliser n’importe quel registre : il y a des conventions d’utilisation. En regardant la section Registers de Guide to x86-64 on voit que r10 est un bon choix (sa valeur est sauvegardé par l’appelant, on peut donc l’utiliser comme on le souhaite).

Avec ces informations en tête, nous pouvons esquisser le squelette de notre fonction de compilation.

1
2
3
4
5
6
7
8
9
10

def compile_bf(bf, memory)
  # movabs r10, @memory (in little-endian)
  asm = "\x49\xBA".b + "#{[memory.address].pack('Q<')}"
  bf.each do |instruction|
    case instruction
      […]
    end
  end
  asm << "\xC3".b # ret
end

On peut voir qu’il y a du code ajouté avant (le prologue) et après (l’épilogue) les instructions générées à partir du code Brainfuck (qui vont être produites dans le bloc each).

Dans le prologue, nous initialisons le registre r10 avec l’adresse de la mémoire allouée pour l’exécution du programme Brainfuck. Deux remarques :

1. les processeurs x86_64 étant little-endian, nous utilisons le format Q< pour écrire l’adresse comme un entier 64-bit little-endian.
2. on utilise la fonction b de la classe String pour que notre chaîne de caractères soit traitées comme une suite d’octets (ce qu’elle est) et non pas comme du texte encodé (en UTF-8 par exemple).

Dans l’épilogue, nous ajoutons l’instruction ret. En effet, notre programme Brainfuck étant compilé en une fonction, il ne faut pas oublier l’instruction ret pour revenir dans le code appelant à la fin de l’exécution.

Compilation des instructions « simples »

Sur les huit instructions du Brainfuck, six peuvent être traduites directement en assembleur, indépendamment du contexte. Les deux dernières ([ et ]) demandent un peu plus d’effort et seront traitées dans la section suivante.

En reprenant la description des instructions de la section précédente et sachant que notre pointeur est stocké dans r10, nous avons les correspondances suivantes :

• > : inc r10.
• < : dec r10.
• + : addb [r10], 1
• - : subb [r10], 1

Pour l’instruction , nous devons utiliser l’appel système read et pour . nous devons utiliser l’appel système write.

Pour faire un appel système en assembleur x86_64 sous Linux ce n’est pas très difficile : il suffit de mettre des valeurs dans des registres, puis d’utiliser l’instruction syscall. Pour savoir quelle valeur mettre dans quel registre, on peut se référer à la page Linux System Call Table for x86 64 par exemple.

Cela nous donne donc

1
2
3
4
5

mov rax, 0      # On veut appeler read.
mov rdi, 0      # On lit sur stdin.
mov rsi, r10    # On veut l’écrire sur la case mémoire actuellement pointée.
mov rdx, 1      # On veut lire seulement 1 octet.
syscall

et

1
2
3
4
5

mov rax, 1      # On veut appeler write.
mov rdi, 1      # On écrit sur stdout.
mov rsi, r10    # On veut écrire la case mémoire actuellement pointée.
mov rdx, 1      # On veut écrire seulement 1 octet.
syscall

Bon, nous avons maintenant l’équivalent en assembleur de nos instructions Brainfuck. Cependant, ce n’est pas suffisant car nous devons générer du code machine directement. Il nous faut donc savoir comment ces instructions sont encodées. Il y a plusieurs façons de faire cela, pour ma part j’ai utilisé rasm2 qui est un utilitaire faisant partie de radare2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

% rasm2 -b 64 -a x86.as 'inc r10'
49ffc2
% rasm2 -b 64 -a x86.as 'dec r10'
49ffca
rasm2 -b 64 -a x86.as 'subb [r10], 1'
41802a01
% rasm2 -b 64 -a x86.as 'addb [r10], 1'
41800201

% rasm2 -b 64 -a x86.as 'mov rax, 1'
48c7c001000000
% rasm2 -b 64 -a x86.as 'mov rdi, 1'
48c7c701000000
% rasm2 -b 64 -a x86.as 'mov rsi, r10'
4c89d6
% rasm2 -b 64 -a x86.as 'mov rdx, 1'
48c7c201000000
% rasm2 -b 64 -a x86.as 'syscall'
0f05

% rasm2 -b 64 -a x86.as 'mov rax, 0'
48c7c000000000
% rasm2 -b 64 -a x86.as 'mov rdi, 0'
48c7c700000000

L’option -b indique la taille des registres et l’option -a l’architecture (une liste complète est disponible via l’option -L).

On peut maintenant compiler à la volée les instructions « simples ».

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Mapping f(Brainfuck instruction) = x86_64 assembly
INSTRUCTIONS_MAPPING = {
  '>' => "\x49\xFF\xC2".b,
  '<' => "\x49\xFF\xCA".b,
  '+' => "\x41\x80\x02\x01".b,
  '-' => "\x41\x80\x2A\x01".b,
  '.' => [0x48, 0xC7, 0xC0, 0x01, 0x00, 0x00, 0x00,
          0x48, 0xC7, 0xC7, 0x01, 0x00, 0x00, 0x00,
          0x4C, 0x89, 0xD6,
          0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00, 0x00,
          0x0F, 0x05].pack('c*'),
  ',' => [0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00,
          0x48, 0xC7, 0xC7, 0x00, 0x00, 0x00, 0x00,
          0x4C, 0x89, 0xD6,
          0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00, 0x00,
          0x0F, 0x05].pack('c*')
}.freeze

def compile_bf(bf, memory)
  asm = "\x49\xBA".b + "#{[memory.address].pack('Q<')}"
  bf.each do |instruction|
    case instruction
    when '>', '<', '+', '-', '.', ','
      asm << INSTRUCTIONS_MAPPING.fetch(instruction)
    when '['
      […]
    when ']'
      […]
    else
      raise "invalid instruction: #{instruction}"
    end
  end
  asm << "\xC3".b
end

On remarque que j’ai ajouté une clause else au case. Cela semble inutile au premier abord, car bf ne contient que des caractères faisant parti du jeu d’instructions du Brainfuck (grâce au select appliqué dans la fonction main). Cependant, ce else est utile pour détecter des erreurs du développeur. Par exemple, dans ma première version du code le caractère . était présent deux fois dans la clause when de la ligne 23 et l’instruction , n’était pas géré. Grâce au else, l’erreur a été très rapidement mise en évidence (et corrigé !).

Compilation des boucles

Il ne reste plus que deux instructions à gérer : [ et ], qui permettent de faire des boucles en Brainfuck.

Pour rappel, l’instruction [ saute à l’instruction suivant le ] correspondant si la valeur de la case mémoire actuellement pointée est égale à zéro. En assembleur ça se traduit par :

1
2

cmpb [r10], 0
jz offset_vers_l_instruction_suivant_]

Dans le cas de ] on fait un saut si la valeur est différente de zéro, ce qui donne :

1
2

cmpb [r10], 0
jnz offset_vers_l_instruction_suivant_[

Le problème étant de calculer les offsets des sauts (surtout dans le cas de [ car on ne connait pas encore la position du ] correspondant au moment où l’on traite [).

Pour résoudre ce problème, nous allons avoir besoin d’une pile et nous allons appliquer les opérations suivantes :

• lorsque l’on rencontre l’instruction [ :
  • on génère l’instruction de comparaison (le cmpb).
  • on empile la position courante (jz_pos) car nous devrons y revenir pour mettre à jour le code généré lorsque l’on trouvera le ] correspondant.
  • on insère un placeholder de 6 octets (6 octets car l’instruction de saut jz est encodée sur 2 octets et l’offset est encodé sur 4 octets).
• lorsque l’on rencontre l’instruction ] :
  • on génère l’instruction de comparaison (le cmpb).
  • on récupère le jz_pos correspondant (sur le dessus de la pile) : il contient l’adresse du placeholder à modifier.
  • on calcule l’offset du saut pour [ : l’offset est calculé entre les deux positions situées juste après les instructions de saut elles-mêmes.
  • on remplace le placeholder par un jz avec l’offset que l’on vient de calculer.
  • on calcule l’offset dans l’autre sens pour ] (pour sauter en arrière, vers le début de la boucle) et on génère l’instruction jnz avec cet offset.

Un petit schéma pour essayer de visualiser tout ça :

Et le code correspondant :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def compile_bf(bf, memory)
  stack = []
  # movabs r10, @memory (in little-endian)
  asm = "\x49\xBA".b + "#{[memory.address].pack('Q<')}"
  bf.each do |instruction|
    case instruction
    when '>', '<', '+', '-', '.', ','
      asm << INSTRUCTIONS_MAPPING.fetch(instruction)
    when '['
      asm << "\x41\x80\x3A\x00".b # cmpb [r10], 0
      stack << asm.size # Save the offset where we will patch the jump.
      # Insert a placeholder of 6 bytes (2 for JZ + 4 for the address).
      asm << "\x0F\x84\x00\x00\x00\x00".b
    when ']'
      raise 'unmatched ]' if stack.empty?
      asm << "\x41\x80\x3A\x00".b # cmpb [r10], 0
      jz_pos     = stack.pop    # Address of the JZ to patch.
      start_loop = jz_pos + 6   # Address of the first instruction of the loop body.
      end_loop   = asm.size + 6 # Address of the first instruction after the loop body.
      # Generate the jump to the start of the loop (using JNZ).
      offset = compute_jump_offset(end_loop, start_loop)
      asm << "\x0F\x85".b << [offset].pack('L<') # L< because little endian!
      # Go back to patch the jump to the end of the loop.
      offset = compute_jump_offset(start_loop, end_loop)
      asm[jz_pos, 6] = "\x0F\x84".b + [offset].pack('L<')
    else
      raise "invalid instruction: #{instruction}"
    end
  end
  raise 'unmatched [' unless stack.empty?
  asm << "\xC3".b # ret
end

La fonction compute_jump_offset est une traduction en Ruby de la fonction C++ compute_relative_32bit_offset d’Eli qui est disponible ici. La seule subtilité c’est que les entiers en Ruby n’ont pas de taille fixe donc il faut bien penser à ne garder que les 32 premiers bits avec un masque.

1
2
3
4
5
6
7
8
9
10
11
12

def compute_jump_offset(from, to)
  if to >= from
    diff = to - from
    raise 'offset too large' unless diff < (1 << 31)
    diff
  else
    # Here the diff is negative, so we need to encode it as 2s complement.
    diff = from - to
    raise 'offset too large' unless (diff - 1) < (1 << 31)
    (~diff + 1) & 0xFFFFFFFF
  end
end

Voilà ! Notre fonction de compilation est complète. Il n’y a plus qu’a tester :).

Benchmark

Le code complet de bf-jit.rb est disponible ici.

Pour mettre en évidence les avantages de la compilation à la volée en terme de performance, j’ai testé bf-jit.rb contre deux autres implémentations parmi celles présentées dans mon premier article sur le Brainfuck :

• rbfi : un interpréteur naïf écrit en Ruby, par Ouranos.
• cbfi : mon interpréteur en C, qui implémente quelques optimisations basiques.

Le programme Brainfuck utilisé pour le benchmark est primes.bf qui est un programme qui calcule les nombres premiers.

1
2
3
4
5
6
7
8

% time ./cbfi "$(cat primes.bf)" <<< 100
[…] 0,95s user 0,00s system 99% cpu 0,953 total

% time ./rbfi.rb primes.bf <<< 100
[…] 493,37s user 0,41s system 99% cpu 8:13,87 total

% time ./bf-jit.rb primes.bf <<< 100
[…] 0,23s user 0,02s system 99% cpu 0,249 total

Pas mal du tout ! Presque 4x plus rapide que la version C ! Et pourtant notre compilateur est très stupide : il traduit le code instruction par instruction.

D’ailleurs, ce comportement naïf est pénalisant sur certains programmes tel que hanoi.bf où mon interpréteur C est plus rapide (grâce à ses optimisations) que bf-jit.rb. Cela étant dit, il nous suffirait d’implémenter les optimisations décrites dans les articles d’Eli pour que notre compilateur repasse en tête :-)

Aller plus loin

Au lieu d’écrire notre code directement en hexadécimal, on peut utiliser un assembleur (comme metasm ou wilson par exemple) pour pouvoir utiliser des mnémoniques et améliorer la lisibilité/souplesse du code.

Par exemple, si l’on utilise metasm pour réécrire le petit code d’exemple de jit.rb on obtient :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

if __FILE__ == $PROGRAM_NAME
  require 'metasm'

  asm = <<-EOS
  mov rax, rdi
  add rax, 4
  ret
  EOS
  code = Metasm::Shellcode.assemble(Metasm::X86_64.new, asm).encoded.data
  func = JitFunction.new(:long, [:long], code)
  begin
    puts func.call(-100)
  ensure
    func.free
  end
end

Ce qui est tout de même un poil plus lisible :)

On pourrait même aller jusqu’à utiliser LLVM (via ruby-llvm) pour générer du code optimisé et devenir facilement multi-plateforme au lieu d’être limité aux processeurs x86_64.

La semaine dernière j’ai aidé à résoudre un problème assez surprenant : une partition racine pleine selon df (ou dfc) :

1
2
3
4

FILESYSTEM               (=) USED      FREE (-)  %USED AVAILABLE  TOTAL MOUNTED ON
[…]
/dev/dm-0                [====================]   100%     15.6G  15.6G /
[…]

Mais lorsque l’on essaye de trouver les coupables via ncdu, la somme est loin de faire 16Go :

1
2
3
4
5
6

.   3.8GiB [##########] /var
    1.2GiB [###       ] /srv
  885.2MiB [##        ] /opt
  223.0MiB [          ] /lib
.  95.4MiB [          ] /etc
[…]

Surprenant !

Les fichiers perdus dans les limbes

Après réflexion, je me suis souvenu que certains fichiers pouvaient rester bloqués dans les limbes. En effet, il faut savoir que, sous Linux, quand un fichier est supprimé (avec rm par exemple), il n’est pas réellement supprimé tant qu’au moins un processus utilise ledit fichier. Par conséquent, même si le fichier n’est plus affiché par ls ou find, il occupe toujours de l’espace sur le disque.

Pour lister ces fichiers, on ne peut pas utiliser les commandes habituelles telles que ls ou find, mais on peut utiliser lsof qui est une commande qui liste les fichiers ouverts (lsof => list open files). La sortie de lsof est très verbeuse, heureusement en lisant sa page de manuel (man 8 lsof) on y trouve l’option L qui peut être suivi d’un nombre. Lorsque L est suivi d’un nombre N, lsof va uniquement lister les fichiers qui sont référencé un nombre de fois strictement inférieur à N. Dans notre cas, comme on veut lister les fichiers supprimés (qui ne sont donc plus référencés) il faut utiliser L1 pour lister les fichier ayant 0 référence.

En combinant lsof +L1 avec la commande sort on peut trier par taille pour voir quels sont les fichiers occupant le plus de place.

La commande finale est donc lsof -s +L1 | sort -nk7 ce qui se traduit par : liste (lsof) la taille (-s) de tout les fichiers supprimés et encore ouvert (+L1) et trie (sort) cette liste de manière numérique (-n) sur le champs 7 (-k7, car c’est le septième champs qui est le champ de la taille).

1
2
3
4
5
6
7

% lsof -s +L1 | sort -nk7

COMMAND  PID        USER   FD   TYPE DEVICE    SIZE NLINK    NODE NAME
conky   5372 grim7reaper    0u   CHR 136,16             0      19 /dev/pts/16 (deleted)
conky   5372 grim7reaper    1u   CHR 136,16             0      19 /dev/pts/16 (deleted)
conky   5372 grim7reaper    2u   CHR 136,16             0      19 /dev/pts/16 (deleted)
systemd  709 grim7reaper  txt    REG  254,2 1018520     0 1619496 /usr/lib/systemd/systemd (deleted)

Cette commande a permis de découvrir que l’espace disque était utilisé par des fichiers temporaires de Terminator.

Terminator et libVTE

Reste à savoir pourquoi Terminator utilise autant d’espace disque.

Tout d’abord il faut savoir que le Terminator en cause ici était configuré pour conserver toutes les sorties des terminaux, sans limite (option Inifinite scrollback). Le problème c’est que les buffers des terminaux sont stockés sur disques et donc que plus les terminaux sont utilisés longtemps et plus il y’a de choses affichées dedans, plus l’espace disque occupé va augmenter.

Ce comportement ne vient pas de Terminator lui-même, mais de la libVTE qui est une bibliothèque utilisée pour implémenter des émulateurs de terminaux. Ce bug touche donc tout les terminaux basés sur libVTE (Terminator, Gnome-Terminal, xfce4-terminal, guake, …).

Ce comportement existe depuis 2009, il est connu et ne sera probablement pas corrigé, alors même que cela peut poser problème (je vous conseille de lire ce rapport de bug qui explique bien la situation)…

Conclusion

Je pense que je vais continuer d’utiliser urxvt :D, qui est l’un des rares terminaux à bien gérer l’espace insécable fine et qui n’est pas basé sur libVTE. Cette petite mésaventure m’aura au moins fait découvrir un aspect fort utile de lsof.

Depuis la version 7.0¹ (sortie le 2009/10/06), GDB embarque un interpréteur Python cela qui permet d’utiliser Python comme langage de scripting pour étendre les fonctionnalités de GDB.

Dans cet article je vais aborder la création de pretty-printer en Python.

Le problème

Comme un exemple vaut mieux qu’un long discours, je vais montrer ici un cas pratique : l’affichage d’adresses IP.

Les systèmes POSIX représentent les adresses via deux structures:

• in_addr pour les IPv4 : une structure qui doit contenir au minimum un champ s_addr de type in_addr_t (qui est équivalent à uint32_t).
• in6_addr pour les IPv6 : une structure qui doit contenir au minimum un champ s6_addr de type uint8_t[16].

Ces informations, parmi d’autres, sont disponibles ici.

De par la définition de ces structures, si on veut les afficher dans GDB on n’obtient quelque chose qui n’est pas très lisible pour un humain.

Soit le programme suivant :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <stdlib.h>

#include <arpa/inet.h>

int main(void)
{
    struct sockaddr_in  ipv4;
    struct sockaddr_in6 ipv6;

    if (inet_pton(AF_INET,  "82.66.107.250", &ipv4.sin_addr) != 1)
        return EXIT_FAILURE;

    if (inet_pton(AF_INET6, "2a01:e35:2426:bfa0:215:ff:fe42:7fd3",
                  &ipv6.sin6_addr) != 1)
        return EXIT_FAILURE;

    return EXIT_SUCCESS;
}

Si on lance GDB dessus en utilisant le fichier de commande suivant :

1
2
3
4
5
6
7
8
9
10

break example.c:17
command
silent
print ipv4->sin_addr
print ipv6->sin6_addr
continue
end

run
quit

On obtient :

1
2
3
4
5
6
7
8

% gdb -q ./example --command=command.gdb 2> /dev/null
Reading symbols from ./example...done.
Breakpoint 1 at 0x8065581: file example.c, line 17.
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".
$1 = {s_addr = 4201333330}
$2 = {__in6_u = {__u6_addr8 = "*\001\016\065$&\277\240\002\025\000\377\376B", <incomplete sequence \323>, __u6_addr16 = {298, 13582, 9764, 41151, 5378, 65280, 17150, 54143}, __u6_addr32 = {890110250, 2696881700, 4278195458, 3548332798}}}
[Inferior 1 (process 2043) exited normally]

Le moins que l’on puisse dire c’est que ce n’est pas super human-friendly ($1 étant l’IPv4 et $2 l’IPv6).

Les pretty-printers

Nous allons créer un module python my_pp. Dans le répertoire my_pp, nous aurons deux fichiers :

1. netinet.py qui contiendra le code des pretty-printers.
2. __init__.py qui se chargera d’enregistrer nos pretty-printers auprès de GDB.

Commençons avec le premier fichier (j’ai omis les docstrings pour raccourcir le code).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from struct import pack
from socket import inet_ntop, AF_INET, AF_INET6

from gdb import lookup_type

class ipv4Printer(object):
    def __init__(self, val):
        self.addr = pack('I', int(val['s_addr']))

    def to_string(self):
        return inet_ntop(AF_INET, self.addr)

class ipv6Printer(object):
    def __init__(self, val):
        # IPv6 addresses have a size of 128 bits (== 16 octets).
        N = 16
        addr = val.cast(lookup_type("uint8_t").array(N))
        self.addr = pack('B'*N, *[int(addr[i]) for i in range(N)])

    def to_string(self):
        return inet_ntop(AF_INET6, self.addr)

Allons y étape par étape.

1
2
3
4

from struct import pack
from socket import inet_ntop, AF_INET, AF_INET6

from gdb import lookup_type

Les adresses IP étant stockées sous forme binaire, on importe le module struct pour pouvoir les manipuler. Le module socket va nous servir à les convertir en chaîne de caractères². Enfin, on importe le module gdb.

1
2
3
4
5
6

class ipv4Printer(object):
    def __init__(self, val):
        self.addr = pack('I', int(val['s_addr']))

    def to_string(self):
        return inet_ntop(AF_INET, self.addr)

Lorsque GDB va instancier un objet ipv4Printer, il va lui passer en argument une structure de type in_addr. Comme dit précédemment, cette structure contient un champ s_addr qui est un uint32_t. Notre méthode d’initialisation se contente donc d’extraire ce champ dans le membre addr de notre objet.

Ensuite, la méthode to_string est appelée par GDB à chaque fois qu’il doit afficher un objet de type in_addr. Cette méthode renvoie la chaîne de caractère représentant l’adresse IP contenue dans addr.

1
2
3
4
5
6
7
8
9

class ipv6Printer(object):
    def __init__(self, val):
        # IPv6 addresses have a size of 128 bits (== 16 octets).
        N = 16
        addr = val.cast(lookup_type("uint8_t").array(N))
        self.addr = pack('B'*N, *[int(addr[i]) for i in range(N)])

    def to_string(self):
        return inet_ntop(AF_INET6, self.addr)

En théorie; la version IPv6 devrait être aussi simple que la version IPv4. En théorie… En pratique c’est malheureusement plus compliqué.

En effet, si POSIX requiert que la structure in6_addr_t possède un champ nommé s6_addr le fait est que, la plupart du temps, ce membre n’existe pas vraiment: c’est un symbole de préprocesseur. En tant que tel, il n’est pas accessible dans GDB (sauf si on utilise certaines options de compilation bien spécifiques telle que -g3 et -gdwarf-2 par exemple). Pis encore, Windows ne définit pas ce membre du tout (Windows ne cherche pas vraiment à être conforme POSIX).

La solution que j’ai trouvée est de traiter la structure in6_addr comme un tableau de 16 octets. Cela fonctionne et me semble relativement portable étant donné que la structure in6_addr est définie comme une union dont l’un des champs est effectivement un uint8_t[16] au moins sur les systèmes d’exploitation suivant :

• Linux
• DragonFlyBSD
• Windows
• FreeBSD
• NetBSD

La méthode __init__ de notre objet va donc caster la valeur puis la stocker dans l’attribut addr. Au niveau de la méthode to_string, c’est quasiment la même chose que pour ipv4Printer (on remplace seulement AF_INET par AF_INET6).

Enfin, l’enregistrement de nos deux classes se fait dans le fichier __init__.py.

1
2
3
4
5
6
7
8

from gdb.printing import RegexpCollectionPrettyPrinter
import netinet

def netinet_pp():
    pp = RegexpCollectionPrettyPrinter("netinet")
    pp.add_printer('in_addr',  '^in_addr$',  netinet.ipv4Printer)
    pp.add_printer('in6_addr', '^in6_addr$', netinet.ipv6Printer)
    return pp

On commence par importer le module gdb.printing, puis nos pretty-printers. L’enregistrement se fait via un objet RegexpCollectionPrettyPrinter (via lequel on peut donner un nom à notre groupe de pretty-printers) dans lequel nous ajoutons nos pretty-printers. Lors de l’ajout, on donne un nom, une expression rationnelle qui va définir les noms des types que nous pouvons afficher, puis la classe du pretty-printer.

Maintenant que le code est fait, voyons comment utiliser tout ça.

La mise en œuvre

La mise en œuvre est très simple, elle peut se faire via le fichier .gdbinit. Il suffit d’y ajouter ces lignes :

1
2
3
4
5
6
7
8
9
10

# Python
python

from sys import path
from gdb.printing import register_pretty_printer

path.insert(0, '/chemin/vers/répertoire/contenant/my_pp')

import my_pp
register_pretty_printer(gdb.current_objfile(), my_pp.netinet_pp())

Je pense que ça se passe de commentaire.

Le résultat

Et maintenant, si on lance GDB sur notre exemple on obtient :

1
2
3
4
5
6
7
8

% gdb -q ./example --command=command.gdb 2> /dev/null
Reading symbols from ./example...done.
Breakpoint 1 at 0x8065581: file example.c, line 17.
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/usr/lib/libthread_db.so.1".
$1 = 82.66.107.250
$2 = 2a01:e35:2426:bfa0:215:ff:fe42:7fd3
[Inferior 1 (process 2424) exited normally]

Ce qui est, il faut l’admettre, bien plus lisible.

Pour conclure, je mentionnerai que la commande info pretty-printer permet d’afficher la liste des pretty-printers actuellement chargé dans GDB. Il est également possible d’utiliser l’affichage « brut » de GDB, sans passer par un pretty-printer (même s’il en existe un pour le type) en utilisant le modificateur /r de la commande print (par exemple print /r toto).

Voilà, ça sera tout pour cette introduction aux pretty-printers. La documentation officielle est ici pour ceux qui veulent approfondir.

Contexte

Premièrement, qu’est-ce que j’entends par « fonction de comparaison » ?
Je parle des fonctions qui prennent deux arguments en entrée et qui renvoie :

• un nombre positif si le premier argument est strictement supérieur au second.
• 0 si les deux arguments sont égaux.
• un nombre négatif si le premier argument est strictement inférieur au second.

Ce genre de fonction est utilisée pour ordonner des éléments (ordre total), et elles sont donc naturellement utilisée par certaines fonctions de tri telles que qsort.

Maintenant, pourquoi est-ce que je parle d’une erreur répandue ?
Et bien parce qu’en tapant « qsort » ou « qsort example » dans un moteur de recherche, je tombe sur ça (il y a aussi des versions correctes, je vous rassure) :

• cplusplus.com
• bien-programmer.fr
• tutorialspoint.com
• anyexample.com

Problème

Alors, quel est le problème ?
Prenons l’exemple donné sur le site cplusplus.com :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* qsort example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}

Si on teste cet exemple, on obtient bien le résultat attendu :

10 20 25 40 90 100

Bien, et si maintenant on utilise¹ :

1

int values[] = { 40, INT_MIN, 100, INT_MAX, 20, INT_MIN + 42 };

Alors là, rien ne va plus ! En sortie on obtient :

40 100 2147483647 -2147483648 -2147483606 20

Ce qui ne correspond pas du tout à un tableau trié par ordre croissant.

Explication

Le souci vient de la fonction de comparaison :

1
2
3
4

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

L’idée derrière cette fonction est que comme on doit renvoyer un nombre positif si a > b, négatif is a < b et 0 si a = b alors autant renvoyer la différence.

En théorie, ça fonctionne. En pratique, les nombres représentables dans un int sont bornés et il y a donc risque d’overflow lorsque l’on approche les valeurs limites. Et en effet, l’opération a - b peut produire un résultat non représentable dans un int.

À toutes fins utiles, je rappelle que les overflow d’entiers signés en C sont un comportement non-défini. Cela vient en partie du fait que le standard du C n’impose rien sur la représentation des entiers signés (signe et magnitude, complément à un ou complément à deux) et ne veut donc pas dicter le comportement attendu pour ce genre de situation.

Solution

La solution est très simple. Étant donné que l’on souhaite faire une fonction de comparaison il suffit d’utiliser les opérateurs de comparaison afin d’éviter tout problème d’overflow :

1
2
3
4
5
6
7
8
9
10
11
12

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;

    if (*left > *right)
        return 1;
    else if (*left < *right)
        return -1;
    else
        return 0;
}

Et pour ceux qui trouvent l’alternative précédente trop verbeuse, il est toujours possible l’utiliser l’idiome suivant :

1
2
3
4
5
6

int compare (const void * a, const void * b)
{
    const int* left = a;
    const int* right = b;
    return (*left > *right) - (*left < *right);
}

Cette version se base sur le fait que les opérateurs > et < renvoie 0 ou 1, ce qui est garanti par le standard (Cf. ISO/IEC 9899:TC3, 6.5.8 Relational operators §6, page 86) :

[...]
Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.)
The result has type int.
[...]

Cette version est donc absolument portable et devrait même fonctionner sur un DS9K :P

J’ai été confronté à ce bogue le 2013/08/25, je n’avais donc pas encore découvert le comportement indéfini lié à offsetof (que j’ai découvert lors de la rédaction de l’article précédent) ce qui explique pourquoi je ne le mentionne pas ici.

Le 2013/08/25, j’ai été confronté à un bogue assez surprenant au premier abord. Comme cela faisait longtemps que je n’étais pas tombé sur un bogue de ce genre, j’ai eu envie de partager le raisonnement que j’ai suivi pour en venir à bout (au cas où cela puisse servir à d’autres) sur le forum ubuntu-fr. Ce bogue fut aussi, d’une certaine façon, ce qui a conduit à l’ouverture de ce blog.

Le contexte

J’étais en train d’implémenter une liste linéaire simplement chaînée. Une liste générique, mais sans utiliser void* comme on le fait traditionnellement. Au lieu de cela, j’avais décidé de m’inspirer d’une méthode assez connue qui est utilisée dans le noyau Linux (utilisation d’une structure de données intrusive).

Le morceau de code qui suit permet d’avoir un aperçu de l’interface de la liste. Il s’agit en fait d’une version minimale du véritable programme d’exemple auquel j’ai retiré la gestion des erreurs (malloc) et la libération de la mémoire allouée car ce n’est pas le sujet ici (ne vous inquiétez pas, dans le programme d’origine tout cela est présent).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

#include "slist.h"

typedef struct
{
    unsigned to;
    slist_node node;
    unsigned from;
} pair_list;

int main(void)
{
    slist_list list;
    pair_list* elt;
    unsigned i;

    /* Initialize the list. */
    slist_init(&list);

    /* Populate the list. */
    for(i = 0; i < 2; ++i)
    {
        elt = malloc(sizeof *elt);
        elt->from = i;
        elt->to   = i+1;
        slist_add(&list, &(elt->node));
    }

    /* Iteration with `slist_foreach_elt`. */
    slist_foreach_elt(&list, elt, pair_list, node)
        printf("from = %u | to = %u\n", elt->from, elt->to);

    return 0;
}

La découverte

Voyons maintenant ce que l’on obtient en sortie en l’exécutant.

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2

from = 1 | to = 2
from = 0 | to = 1

1
2
3

from = 1 | to = 2
from = 0 | to = 1
zsh: segmentation fault (core dumped)

Tiens, tiens. Comme c’est intéressant : un bogue qui n’apparaît que lorsque l’on active les optimisations, et sur un seul compilateur en plus !

Quand on a une différence de comportement entre deux compilateurs, il y a deux solutions possibles :

1. l’un des deux compilateurs a un bogue (peu probable, mais cela arrive).
2. notre code contient :
   • un comportement non défini (undefined behavior, que je vais abréger par UB par la suite).
   • OU un comportement non spécifié (unspecified behavior).
   • OU un comportement dépendant de l’implémentation (implementation-specific behavior).

La différence entre les trois étant parfois oubliée, je vais faire un petit rappel ici. Tout d’abord, il faut savoir que le standard décrit une machine abstraite C (C abstract machine) qui peut être vu comme un interpréteur C.

• un comportement dépendant de l’implémentation (comme la taille d'un int par exemple) peut être vu comme un paramètre de la machine abstraite. Le standard peut proposer plusieurs comportements possibles, auquel cas l’implémentation doit en choisir un parmi ceux proposés. Si le standard ne spécifie rien, alors l’implémentation est libre de choisir son comportement. Dans tous les cas, l’implémentation doit documenter ses choix (on trouve ceux de GCC ici).
• un comportement non spécifié (comme l’ordre d’évaluation des arguments d’une fonction) peut être vu comme un comportement non-déterministe de la machine abstraite. Comme pour un comportement dépendant de l’implémentation, le standard peut proposer plusieurs possibilités et l’implémentation doit faire un choix parmi eux. Sinon, elle est libre de choisir le comportement qu’elle souhaite. En revanche, ces comportements ne sont pas forcément documentés par l’implémentation.
• un comportement non défini (comme déréférencer un pointeur NULL) est un comportement pour lequel le standard n’offre aucune garantie. Un compilateur qui rencontre un UB est libre de faire ce qu’il veut, ABSOLUMENT TOUT ce qu’il veut. Ce qui inclut (entre autres) :
  • produire une erreur de compilation
  • ignorer le problème
  • supprimer le code qui contient l’UB
  • ignorer le standard (oui, un seul UB à un endroit rend TOUT le code indéfini)
  • générer un programme qui va crasher à l’exécution
  • générer un programme qui va produire de mauvais résultats
  • générer un programme qui va fonctionner comme prévu (et oui, cela arrive)
  • générer un programme qui va formater votre disque dur
  • générer un programme qui va afficher 42
  • faire sortir des démons de votre nez.

Ceci dit, les UB ont aussi leurs bons côtés : c’est en partie grâce à leur existence que les compilateurs C peuvent faire de nombreuses optimisations. À ce sujet, je vous conseille cet excellent article en trois parties écrit par Chris Lattner (qui sait donc très bien de quoi il parle) :

• What Every C Programmer Should Know About Undefined Behavior #1/3
• What Every C Programmer Should Know About Undefined Behavior #2/3
• What Every C Programmer Should Know About Undefined Behavior #3/3

Tant que j’en suis à donner des liens, cet article en trois parties de John Regehr est aussi très instructif sur les UB :

• A Guide to Undefined Behavior in C and C++, Part 1
• A Guide to Undefined Behavior in C and C++, Part 2
• A Guide to Undefined Behavior in C and C++, Part 3

Étant donné que :

1. je connaissais les articles précédemment cités.
2. mon bogue apparaît seulement avec les optimisations activées (avec clang, il est présent à partir de O1 et avec gcc le programme s’exécute correctement quel que soit le niveau d’optimisation).
3. mon code joue avec des pointeurs, des adresses, des structures et des macros.

Je suis donc directement partie sur la solution 2.

Le bogue

J’ai commencé par utiliser Memcheck sur la version compilé et optimisé par clang (entre temps, j’ai pris soin de recompiler avec le flag -g en plus de -O2 pour avoir les informations de déboguage).

Voilà le résultat :

1
2
3

==7949== Invalid read of size 4
==7949==    at 0x4006A0: main (min_bug.c:34)
==7949==  Address 0xfffffffffffffff8 is not stack'd, malloc'd or (recently) free'd

Petite précision utile : la ligne 34 c’est le printf dans la boucle.

Donc a priori, la boucle fait trop d’itérations et essaye d’afficher des éléments en dehors de la liste. Étrange, sachant que le même code sans optimisations est tout à fait correct (Memcheck ne rapporte rien d’anormal). Donc une boucle tout à fait correcte, deviens boguée après optimisations. Hum…

Suite à cela, j’ai tenté de passer par gdb. En vain… La variable d’intérêt, elt, était optimized out (même en O1, et comme en O0 le bogue ne se manifeste pas…).

Du coup, j’ai ajouté un printf pour afficherelt et elt->node (ce sont les variables utilisées dans la condition d’arrêt du foreach) à chaque itération et j’ai pu constater que quand elt->node atteint la valeur nécessaire à l’arrêt de la boucle, et bien cette dernière ne s’arrête pas.

Bien, ma condition semble avoir disparue, c’est très ennuyeux ça. Je dois le vérifier. Et pour cela, il n’y a qu’une seule façon fiable : regarder le code assembleur généré.

En avant donc. Jetons d’abord un coup d’œil au code produit par gcc (je commence par celui là, car je sais que même optimisé ma boucle est toujours correcte).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

.LVL4:
        .loc 1 33 0
        movq    %rsp, %rdi
        call    slist_first
.LVL5:
        leaq    -8(%rax), %rdx
.LVL6:
        movq    %rax, %rbx
        testq   %rax, %rax
        je      .L2
.L3:
        .loc 1 34 0 discriminator 2
        movl    16(%rdx), %esi
        movl    (%rdx), %edx
.LVL7:
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
.LVL8:
        .loc 1 33 0 discriminator 2
        movq    %rbx, %rdi
        call    slist_next
.LVL9:
        leaq    -8(%rax), %rdx
.LVL10:
        movq    %rax, %rbx
        testq   %rax, %rax
        jne     .L3

Dans les dernières lignes on voit bien une comparaison (testq) suivi d’un saut conditionnel (jne) en début de boucle : tout va bien.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

.Ltmp13:
# BB#2:
        leaq    8(%rsp), %rdi
        .loc    1 33 0                  # examples/min_bug.c:33:0
.Ltmp14:
        callq   slist_first
        movq    %rax, %rbx
        .align  16, 0x90
.LBB0_3:                                # =>This Inner Loop Header: Depth=1
        .loc    1 34 0                  # examples/min_bug.c:34:0
        movl    -8(%rbx), %edx
        movl    8(%rbx), %esi
        movl    $.L.str, %edi
        xorb    %al, %al
        callq   printf
        .loc    1 33 0                  # examples/min_bug.c:33:0
        movq    %rbx, %rdi
        callq   slist_next
        movq    %rax, %rbx
        jmp     .LBB0_3

Et là : BAM !!!
En plein dans le mille.
La dernière instruction de la boucle est un saut inconditionnel en début de boucle. Pas de cmp ou test. Mais un bon gros jmp tout ce qu’il y a de plus inconditionnel. La différence saute au yeux !

C’est donc une belle boucle infinie, ce qui explique que je continue à boucler même après avoir rencontré ma condition d’arrêt (et donc cela explique également le fait que j’aille lire des adresses pourries qui me font faire une jolie Segmentation Fault).

L’explication

Maintenant, on est sûr que le problème vient de la boucle, et donc de slist_foreach_elt. Regardons donc ça de plus près :

1
2
3
4

#define slist_foreach_elt(list, curr, type, fieldname)         \
    for (curr = slist_elt(slist_first(list), type, fieldname); \
         &(curr->fieldname) != NULL;                           \
         curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Hooooo yeaaah :)

Sachant que slist_elt est aussi une macro :

1
2

#define slist_elt(node, type, fieldname) \
    ((type*)((char*)(node) - offsetof(type, fieldname)))

Bon, ça peut faire peur de voir ça comme ça, à froid et sans explication :D
Mais en réalité c’est très simple, et c’est le cœur même de l’astuce qui permet d’avoir une liste générique sans passer par du void*. Cela dit, je ne vais pas m’étendre sur le sujet du pourquoi du comment ça fonctionne (voire l’article précédent pour cela).

Donc sans plus d’explications, je vous montre la ligne fautive (qui est belle est bien dans le foreach) :

&(curr->fieldname) != NULL;                          \

Ça peut sembler bizarre comme test, mais en fait ça tient la route (enfin presque, à un détail près et c’est bien pour cela que ça plante)
Pour information, voilà la version que l’on trouve dans le noyau Linux :

&pos->member != (head);    \

C’est presque exactement le même code. À un détail près.

Détail qui vient du fait que la version Linux est une liste circulaire doublement chaînée. Et le point crucial ici est : circulaire.

Car grace à cette propriété, la condition d’arrêt est un test contre la tête de la liste, pas contre NULL.

Différence minime ? C’est ce que je pensais. Mais pas du tout, c’est une énorme différence : la différence entre un code correct et un UB.

Pas à pas

Lorsque je suis sur le dernier nœud (dont le pointeur next vaut NULL), je vais exécuter cette ligne (la partie incrémentation du foreach) :

curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Donc ici, je vais appeler slist_elt avec le contenu du pointeur next (car j’appelle slist_next), c’est-à-dire avec NULL.

Cela donne :

((type*)((char*)(node) - offsetof(type, fieldname)))

Et donc dans le cas présent :

((pair_list*)((char*)(NULL) - offsetof(pair_list, node)))

offsetof renvoie, comme son nom l’indique, l’offset (en byte) d’un champ dans une structure.

Ici, je veux l’offset de mon nœud dans la structure. Ça me retourne donc 8 (en effet, dans la structure pair_list il y a un unsigned avant ce champ, et les unsigned sur ma machine font 4 bytes et il y a 4 bytes de padding pour aligner le champ suivant).

NULL étant défini, au niveau du code source (ce n’est pas toujours vrai après compilation), comme étant 0 cela donne donc : 0 - 8.

NULL étant un pointeur et les pointeurs étant non signés et sur 64 bits (sur ma machine), on obtient l’adresse suivante : 0xfffffffffffffff8
Tiens, c’est l’adresse qui était apparue dans Valgrind ça ;)

Donc après exécution de cette partie « incrémentation » de la boucle for, on retourne au début de la boucle et on va tester la condition :

&(curr->fieldname) != NULL;                          \

Ce qui donne dans mon cas :

&(elt->node) != NULL;                          \

curr vaut 0xfffffffffffffff8, l’offset du champ auquel je souhaite accéder est 8. Cela donne donc 0 quand je les additionne. C’est bien égal à NULL, ma boucle s’arrête et c’est parfait.

Oui… Mais non !

Car mon implémentation contient un UB et donc le compilateur peut produire un autre code.

Du point de vue de la norme

Voici quelques extraits choisis de la norme du C99 :

6.3.2.3 Pointers
[…]
3
An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
[…]

Et :

6.5.6 Additive operators
[…]
7
For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

8
When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.
[…]

Réfléchissons un peu. Qu’est-ce que je fais dans cette condition :

&(elt->node) != NULL;                          \

Je compare l’adresse d’un champ de ma structure (donc l’adresse d’un objet) avec NULL (qui ne peut pas être l’adresse d’un objet, cf. §6.3.2.3/3), partant de là le compilateur sait que le test ne renverra jamais faux et il peut donc le supprimer.

De manière générale, toute opération arithmétique avec un pointeur NULL débouche sur un UB. En effet, la condition 6.5.6/8 sera toujours violé (vu que le §6.3.2.3/3 garanti que NULL est différent de tout sauf de lui-même, le résultat de l’opération ne pourra jamais pointer sur le même objet que NULL (vu que par définition il ne pointe sur rien)).
Même faire NULL - NULL c’est un UB. C’est presque le même principe que précédemment, sauf que c’est le §6.5.6/9 au lieu de §6.5.6/8 qui s’applique (je laisse les curieux consulter la norme).

Pour terminer sur une petite remarque, la norme du C++ est un peu plus défini à ce niveau-là car elle autorise deux opérations arithmétiques sur les pointeurs nuls :

• NULL + 0 ou NULL - 0 renvoie NULL
• NULL - NULL renvoie 0

Pour citer la norme :

5.7 Additive operators
[…]
7
If the value 0 is added to or subtracted from a pointer value, the result compares equal to the original pointer value. If two pointers point to the same object or both point one past the end of the same array or both are null, and the two pointers are subtracted, the result compares equal to the value 0 converted to the type std::ptrdiff_t.
[…]

Si vous voulez en savoir plus à propos de pourquoi C++ supporte cela, je vous conseille la lecture de cet article.

La solution

Comme le problème vient du fait d’appeler slist_elt avec NULL il suffit de reformuler la boucle for pour éviter ce cas de figure :

1
2
3
4
5

#define slist_foreach_elt(list, curr, type, fieldname)                     \
        for (curr = slist_elt(slist_first(list), type, fieldname);         \
             curr != NULL;                                                 \
             curr = curr->fieldname.next == NULL ? NULL :                  \
                    slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Et le problème est résolu.

Deux autres solutions possibles :

• implémenter une liste circulaire (comme le noyau Linux), du coup on testera contre l’adresse de la tête.
• créer un nœud global dont l’adresse servira de valeur nulle, on fera donc la comparaison contre ce nœud au lieu de NULL.

Le mot de la fin

• Tester son code avec plusieurs compilateurs, c’est très utile.

• Le diable se cache dans les détails.

• Rien n’est magique, tout est logique (même si pour remonter le fil, il faut parfois des connaissances en standard du C, optimisations faites par les compilateurs et lecture de l’assembleur produit ^^).

Contrairement à d’autres langages (tels que C++, Ada, Java, …) le C n’offre pas de réel support pour la programmation générique. Cela ne signifie pas que la programmation générique est impossible en C, par contre elle nécessite plus d’effort pour être mise en œuvre. Dans cet article, je vais présenter deux approches :

1. une approche à base de void*, que je nomme approche « traditionnelle ».
2. une approche intrusive, sur laquelle je m’attarderai un peu plus car elle me semble moins connue.

Dans la suite de cet article, je vais prendre l’exemple d’une liste simplement chaînée. En effet, c’est une des structures de données de bases et on la retrouve dans d’autres structures de données (certaines tables de hachage par exemple) ou algorithmes. Elle peut même servir de support à un langage (comme les dialectes Lisp où tout est liste, le programme lui-même y compris).

Approche « traditionnelle »

L’approche la plus courante (on la retrouve dans la GLib et les EFL entre autres) est l’utilisation d’un pointeurvoid*. Pour implémenter une liste simplement chaînée générique on pourrait donc avoir le code suivant :

1
2
3
4
5
6
7
8
9
10
11

/* Head of a singly-linked list. */
typedef struct slist_s {
    size_t length;              /* List length. */
    struct slist_node_s* first; /* List head.   */
} slist;

/* A node of a singly-linked list. */
typedef struct slist_node_s {
    struct slist_node_s* next; /* Next element. */
    void* data;                /* User data.    */
} slist_node;

Ici j’ai choisi d’avoir une structure à part pour la tête (ce qui permet d’avoir accès à longueur de la liste sans avoir à la parcourir), mais ce n’est qu’un détail d’implémentation. Chaque nœud de la liste contient un pointeur vers le nœud suivant et un pointeur void* sur les données.

Maintenant que la liste est définie, il faudrait stocker quelque chose dedans. Je vais partir sur une structure qui représente un labyrinthe :

1
2
3
4
5
6
7
8
9
10
11

/* A cell of the maze. */
typedef unsigned char Cell;

/* A Maze. */
typedef struct maze_s {
    Cell* maze;
    size_t m;   /* Number of lines.             */
    size_t n;   /* Number of columns.           */
    size_t in;  /* Index of the starting point. */
    size_t out; /* Index of the exit.           */
} Maze;

En combinant les deux fichiers précédents on peut donc créer une liste de labyrinthes. Cela peut être représenté graphiquement de la manière suivante :

L’avantage de cette approche est qu’elle est relativement naturelle et simple à comprendre. En revanche, elle comporte quelques inconvénients :

1. le fait d’utiliser un pointeur pour les données stockées implique qu’il faudra presque toujours allouer de la mémoire pour les données. On se retrouve donc avec deux allocations par élément de la liste : allocation de la donnée et allocation du nœud lui-même.

2. un autre souci, même s’il est probablement rarement ressenti dans la plupart des cas, est celui des performances : à chaque fois que l’on veut accéder à un élément de la liste à partir du nœud on doit déréférencer un pointeur. Ce n’est pas gratuit.

L’impact du point 1 peut être réduit en utilisant une stratégie d’allocation adaptée (la GLib propose quelque chose dans ce sens).

Si la perte de performance due au point 2 se fait vraiment sentir, il est toujours possible remplacer l’implémentation naïve de la liste par une liste « déroulée » afin d’augmenter la localité des données et de bénéficier de l’usage du cache.

Approche intrusive

Définition

Tout d’abord, il me semble utile de définir ce que l’on appelle une structure de données intrusive.

Dans le cas « normal », le conteneur et le contenu sont totalement indépendants. Le conteneur n’a pas besoin de savoir s’il va servir à stocker des int ou une structure Maze pour être défini. De même, une structure Maze n’a pas besoin de savoir si elle va être stockée dans une liste pour être définie (souvenez vous de la première partie de cet article : slist.h et maze.h sont totalement indépendants).

En revanche, dans le cas d’une structure de données intrusive, la donnée contenue (la structure Maze dans mon exemple) devra être définie en tenant compte du conteneur (dans notre exemple, cela signifie que maze.h dépendra de slist.h).

Mise en œuvre

La liste est toujours indépendante de son contenu (comme dans l’approche « traditionnelle »).

1
2
3
4
5
6
7
8
9
10

/* Head of a singly-linked list. */
typedef struct slist_s {
    size_t length;              /* List length. */
    struct slist_node_s* first; /* List head.   */
} slist;

/* A node of a singly-linked list. */
typedef struct slist_node_s {
    struct slist_node_s* next; /* Next element. */
} slist_node;

Définition quasiment identique à la définition précédente. À un détail près : chaque nœud de la liste ne contient qu’un pointeur vers le nœud suivant et rien d’autre. Aucune référence à son contenu (le champ data a disparu).

En effet, le lien entre la liste et la donnée est maintenant embarqué dans la donnée elle-même (on voit bien le côté intrusif) comme le prouve le nouveau champ node ajouté à la structure Maze :

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include "slist.h"

/* A cell of the maze. */
typedef unsigned char Cell;

/* A Maze. */
typedef struct maze_s {
    Cell* maze;
    slist_node node;
    size_t m;   /* Number of lines.             */
    size_t n;   /* Number of columns.           */
    size_t in;  /* Index of the starting point. */
    size_t out; /* Index of the exit.           */
} Maze;

En combinant les deux fichiers précédents on peut donc créer une liste de labyrinthes. Cela peut être représenté graphiquement de la manière suivante (on voit bien la différence par rapport à l’approche « traditionnelle ») :

Avec cette approche, nous n’avons plus les inconvénients dus à l’utilisation de void* :

• plus besoin d’allouer le nœud ET la donnée : une seule allocation suffit.
• plus de déréférencement pour accéder à la donnée à partir du nœud.

Contrairement à ce que l’on pourrait penser, une liste intrusive n’est pas plus difficile à utiliser qu’une liste « traditionnelle » et ne nécessite pas plus de code. D’ailleurs, on retrouve ces structures intrusives dans le noyau Linux (liste doublement chaînée et arbre rouge-noir par exemple), dans l’en-tête sys/queue.h chez les *BSD (Linux en propose aussi une implémentation) et dans les EFL pour ne citer que quelques exemples connus.

Cependant, cette approche n’est pas parfaite non plus :

1. on utilise de l’espace pour le nœud de la liste même si la donnée n’est pas stockée dans une liste.
2. il faut avoir le contrôle sur la définition des données que l’on veut stocker afin pouvoir ajouter le membre nécessaire à l’utilisation de la liste.
3. il faut avoir un moyen d’accéder à la donnée à partir d’une référence au nœud.

Les problèmes 1 et 2 peuvent être contournés en encapsulant la donnée dans une structure dédiée.

1
2
3
4
5
6
7
8

struct Data {
    /* Interesting fields. */
};

struct data_wrapper {
    struct Data       data;
    struct slist_node node;
};

Cependant, on perd la facilité d’utilisation.

La solution au problème 3 sera abordée plus loin dans cet article.

Exemple d’utilisation

Voici un petit exemple d’utilisation : on crée une liste de 5 éléments, on l’affiche puis on libère la mémoire.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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

#include "slist.h"

typedef struct {
    unsigned to;
    slist_node node;
    unsigned from;
} pair_list;

int main(void)
{
    slist list;
    slist_node* curr;
    slist_node* tmp;
    pair_list*  elt;
    unsigned i;
    /* Initialize the list. */
    slist_init(&list);
    /* Populate the list. */
    for (i = 0; i < 5; ++i) {
        elt = malloc(sizeof *elt);
        if (elt == NULL)
            goto failure;

        elt->from = i;
        elt->to   = i+1;
        slist_add(&list, &(elt->node));
    }
    /* Display the list. */
    slist_foreach(&list, curr) {
        elt = slist_elt(curr, pair_list, node);
        printf("from = %u | to = %u\n", elt->from, elt->to);
    }
    /* Free the list. */
    slist_foreach_safe(&list, curr, tmp) {
        elt = slist_elt(curr, pair_list, node);
        slist_del(&list);
        free(elt);
    }
    return EXIT_SUCCESS;

/* Error handling. */
failure:
    if (!slist_is_empty(&list)) {
        slist_foreach_safe(&list, curr, tmp) {
            elt = slist_elt(curr, pair_list, node);
            slist_del(&list);
            free(elt);
        }
    }
    return EXIT_FAILURE;
}

Lignes 6-10 on définit notre structure (qui pourrait représenter un intervalle). On n’oublie pas d’y intégrer un membre slist_node afin de pouvoir en faire une liste.

Ligne 14 on déclare notre liste puis on l’initialise ligne 20. S’en suit une boucle (lignes 22-30) pour la peupler : on alloue 5 structures et on les ajoute à la liste les unes à la suite des autres. On remarque que pour ajouter un élément à la liste on ne passe pas la structure elle-même mais uniquement son champ node (ligne 29, second paramètre de slist_add).

La seconde boucle (lignes 32-35) affiche le contenu de notre liste. slist_foreach permet de parcourir la liste nœud par nœud. À partir du nœud, on récupère notre structure et on l’affiche.

Enfin, la dernière boucle (lignes 37-41) libère la mémoire allouée. On remarque que l’on supprime d’abord le nœud de la liste via slist_del avant de libérer la mémoire allouée à notre structure (ce qui est logique étant donné que la structure contient le nœud, si on la désalloue en premier on perd l’accès au nœud).

L’exécution de ce code nous donne :

1
2
3
4
5

from = 4 | to = 5
from = 3 | to = 4
from = 2 | to = 3
from = 1 | to = 2
from = 0 | to = 1

Le code est relativement clair et concis, rien de bien compliqué. Cependant, la ligne 33 nous rappelle le problème 3 : comment peut-on récupérer la structure à partir du nœud ?

Dans l’approche traditionnelle, c’est très simple : étant donné que le nœud contient un pointeur sur les données, il suffit de faire node->data pour accéder aux données. Mais dans l’approche intrusive, c’est la donnée qui contient notre nœud : comment peut on accéder à une structure à partir d’un de ses champs ?

Solution

Champ en première position

La norme (ISO/IEC 9899:TC3, 6.7.2.1 Structure and union specifiers § 13, page 103) nous dit :

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

Cela signifie qu’il n’y a jamais de padding avant le premier membre d’une structure et que son adresse correspond donc à l’adresse de la structure elle-même.

Par conséquent, si le champ slist_node est le premier de la structure, il suffit d’un simple cast pour obtenir l’adresse de la structure. Cette solution est très simple et très efficace (un cast en lui-même ne coute rien à l’exécution) mais souffre de deux inconvénients :

• manque de flexibilité : l’utilisateur doit faire en sorte que le champ slist_node soit le premier de la structure.
• il est impossible de stocker la structure dans plus d’une liste (comme cette structure qui peut à la fois être dans une liste de bus (champ node) et dans une liste de bus enfant (champ children)) car on ne peut avoir qu’un seul slist_node en première position.

Utilisation d’offsetof

La solution pour être indépendant de la position du champ (et donc de pouvoir avoir plusieurs champs slist_node par structure) est d’utiliser une macro méconnue mais pourtant fort utile : offsetof (définie dans stddef.h).

Cette macro prend deux arguments :

1. un nom de structure (pair_list par exemple).
2. un nom de champ (node par exemple).

Elle renvoie alors l’offset¹ du champ dans la structure, en byte². À partir de là, c’est très simple : il suffit de calculer l’offset via offsetof puis de soustraire cette valeur à l’adresse du champ qui contient le nœud afin d’obtenir l’adresse de la structure.

Pour éviter de se retrouver avec une dépendance au nom du champ, on passe par la macro suivante :

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * Returns a pointer to the structure which contains the node.
 *
 * \param node      a list node (slist_node*).
 * \param type      type of the structure which contains the node.
 * \param fieldname name of the node (field name) in the structure.
 *
 * \pre `node` must be not NULL.
 *
 * \remarks Complexity: O(1)
 */
#define slist_elt(node, type, fieldname) \
 ((type*)((char*)(node) - offsetof(type, fieldname)))

Cette macro prend trois arguments :

1. l’adresse du nœud (l’adresse du champ slist_node).
2. le type de la structure (pair_list par exemple) : nécessaire pour convertir le type de l’adresse retournée.
3. le nom du champ slist_node utilisé comme premier argument.

Seul point un peu délicat : il faut absolument convertir node en char* sinon la soustraction ne va pas renvoyer l’adresse que l’on souhaite. En effet, soit P un pointeur T* et N un nombre entier : P-N est équivalent à P-N*sizeof(T) (arithmétique des pointeurs de base). Or, l’offset renvoyé par offsetof est exprimé en byte, il faut donc faire la soustraction avec un pointeur sur un type T vérifiant sizeof(T)==1. Sachant que la norme (ISO/IEC 9899:TC3, 6.5.3.4 The sizeof operator § 3, page 80) nous dit :

When applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1.

sizeof(char) renvoyant toujours 1 par définition, il suffit donc de convertir node en char* avant la soustraction pour obtenir le résultat souhaité.

Cependant, cette solution a un gros problème³ : elle contient un comportement indéfini ! En effet, l’arithmétique des pointeurs n’est pas aussi simple qu’elle en à l’air. Il y a un certains nombre de règles à respecter, parmi lesquelles ISO/IEC 9899:TC3, 6.5.6 Additive operator § 7, page 83 :

For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

et ISO/IEC 9899:TC3, 6.5.6 Additive operator § 8, page 83 :

[...]
If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.
[...]

Qu’est ce que cela implique dans notre cas ?

On applique une soustraction à un pointeur qui pointe sur le champ slist_node d’une structure. De manière évidente, ce pointeur ne pointe pas sur un élément contenu dans un tableau donc la première règle que j’ai cité va être appliquée et on va considérer node comme un pointeur sur le premier élément d’un tableau de char (et oui, on convertit node en char* avant d’appliquer la soustraction) de taille 1. Jusque là, on est sauf.

Ensuite, on applique notre soustraction. On va donc soustraire un certain nombre de byte à l’adresse contenue dans le pointeur : le résultat pointera donc à une adresse située avant node. Et là, la seconde règle va nous frapper : le pointeur node et l’adresse résultante ne pointe pas sur le même tableau (étant donné que l’adresse résultante pointe avant le tableau), on a donc un undefined behavior (comportement indéfini). GAME OVER !

Conclusion

En conclusion, le choix entre les deux approches dépend principalement de vos objectifs, de vos contraintes et de vos données.

Si les données peuvent exister de manière indépendante, en dehors de toute structure, la première approche est probablement plus logique. De la même manière, si ce sont des données que vous ne pouvez pas modifier pour y ajouter les champs nécessaires, il est probablement plus pratique d’utiliser l’approche « traditionnelle ».

D’un autre côté, si les données font nécessairement partie d’une liste, on peut envisager l’approche intrusive (en plaçant le champ requis en premier dans la structure). En revanche, si les données doivent pouvoir être stockées dans plusieurs conteneurs à la fois il faudra revenir à la première approche ou utiliser l’approche à base d’offsetof (tout en étant conscient que cela se base sur un comportement indéfini et qu’un compilateur pourrait « casser » le code en l’optimisant).

D’autres critères peuvent bien sûr entrer en compte (si les ajouts/suppressions sont très frèquents, une approche intrusive peut être plus efficace). Il n’y a pas de règle absolue en la matière.

Téléchargement

Pour ceux que cela intéresse, le code complet de la liste simplement chaînée (version intrusive) est disponible ici.

Attention : Ce code ayant été écrit longtemps avant la rédaction de cet article, il est donc basé sur la méthode offsetof qui contient un comportement indéfini (dont j’ignorai l’existence au moment de l’écriture du code).

Le code est sous licence BSD-3. Il est écrit en C89 et aucune dépendance particulière n’est requise (hormis Check pour les tests unitaires). La compilation se fait via CMake, une documentation peut être générée par Doxygen. Deux exemples sont disponibles dans le dossier examples.

Le crackme étudié dans cet article provient d’ici.

Cinquième crackme, et cette fois nous allons travailler non pas sur du code machine, mais sur du bytecode Python.

Un fichier Python compilé reste un fichier binaire, donc nous pouvons commencer par la traditionnelle commande strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

% strings ch19.pyc
__main__u$
Welcome to the RootMe python crackmeu
Enter the Flag: u'
I know, you love decrypting Byte Code !i
You Winu
Try Again !N(
__name__u
printu
inputu
PASSu
KEYu
SOLUCEu
KEYOUTu
appendu
ordu
len(
crackme.pyu
<module>

Bon rien de bien concluant. Il est maintenant temps de se renseigner sur ce fameux fichier de bytecode, et plus particulièrement sur son format. Après quelques recherches, je suis tombé sur ce fil de la liste de diffusion Python-ideas. La partie intéressante est la suivante :

Currently .pyc files use a very simple format:

- MAGIC number (4 bytes, little-endian)
- last modification time of source file (4 bytes, little-endian)
- code object (marshaled)

Et bien ça c’est une bonne nouvelle :-). Le format de ce fichier est extrêmement simple. Deux entiers 32-bit et un objet code sérialisé.

Cela dit, le fait que l’objet code soit sérialisé via le module marshal plutôt que via le module pickle implique qu’il va nous falloir utiliser une version de Python relativement proche de celle qui a généré le bytecode, sinon on risque de ne pas pouvoir désérialiser l’objet.
Le crackme ayant été publié le 3 juillet 2013, je vais tenter ma chance avec le Python 3.3 de mon Archlinux.

Essayons donc de lire ce fichier :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

% bpython
>>> import marshal
>>> import struct
>>> import time
>>> pyc = open('ch19.pyc', 'rb')
>>> magic_number = struct.unpack('<i', pyc.read(4))[0]
>>> hex(magic_number)
'0xa0d0c4f'
>>> timestamp = struct.unpack('<i', pyc.read(4))[0]
>>> time.strftime('%Y/%m/%d', time.localtime(timestamp))
'2013/07/02'
>>> code = marshal.load(pyc)
>>> code
<code object <module> at 0x7fb7b60e80c0, file "crackme.py", line 8>
>>> pyc.close()

Ok, c’est bien du Python 3. À titre de comparaison, voilà ce qui arrive si l’on essaye de lire le fichier avec du Python 2.7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

% python2
Python 2.7.5 (default, Sep  6 2013, 09:55:21)
[GCC 4.8.1 20130725 (prerelease)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import marshal
>>> import struct
>>> import time
>>> pyc = open('ch19.pyc', 'rb')
>>> magic_number = struct.unpack('<i', pyc.read(4))[0]
>>> hex(magic_number)
'0xa0d0c4f'
>>> timestamp = struct.unpack('<i', pyc.read(4))[0]
>>> time.strftime('%Y/%m/%d', time.localtime(timestamp))
'2013/07/02'
>>> code = marshal.load(pyc)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: bad marshal data (unknown type code)

Ok, on arrive donc bien à désérialiser notre binaire en un objet code. Et maintenant, on fait quoi avec cet objet ?
C’est là que l’excellente et très complète bibliothèque standard de Python intervient. Dans cette bibliothèque on trouve une section Python Language Services qui contient le module dis. Et c’est exactement ce qu’il nous faut !

Allez, faisons un petit script pour désassembler ce fichier compilé et avoir du bytecode à nous mettre sous la dent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#!/usr/bin/env python3

import dis
import marshal
import struct
import sys

def disassemble(filepath):
    with open(filepath, 'rb') as pyc:
        # Read the magic number.
        _ = struct.unpack('<i', pyc.read(4))
        # Read the timestamp
        _ = struct.unpack('<i', pyc.read(4))
        # Read the code.
        code = marshal.load(pyc)
    dis.disassemble(code)

if __name__ == '__main__':
    if len(sys.argv) == 2:
        disassemble(sys.argv[1])
    else:
        print('Error: missing argument', file=sys.stderr)
        print('Usage: {} file.pyc'.format(sys.argv[0]))

Et maintenant, appliquons-le à notre crackme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

% ./disass.py ch19.pyc
  8           0 LOAD_NAME                0 (__name__)
              3 LOAD_CONST               0 ('__main__')
              6 COMPARE_OP               2 (==)
              9 POP_JUMP_IF_FALSE      219

  9          12 LOAD_NAME                1 (print)
             15 LOAD_CONST               1 ('Welcome to the RootMe python crackme')
             18 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             21 POP_TOP

 10          22 LOAD_NAME                2 (input)
             25 LOAD_CONST               2 ('Enter the Flag: ')
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 STORE_NAME               3 (PASS)

 14          34 LOAD_CONST               3 ('I know, you love decrypting Byte Code !')
             37 STORE_NAME               4 (KEY)

 16          40 LOAD_CONST               4 (5)
             43 STORE_NAME               5 (I)

 17          46 LOAD_CONST               5 (57)
             49 LOAD_CONST               6 (73)
             52 LOAD_CONST               7 (79)
             55 LOAD_CONST               8 (16)
             58 LOAD_CONST               9 (18)
             61 LOAD_CONST              10 (26)
             64 LOAD_CONST              11 (74)
             67 LOAD_CONST              12 (50)
             70 LOAD_CONST              13 (13)
             73 LOAD_CONST              14 (38)
             76 LOAD_CONST              13 (13)
             79 LOAD_CONST               7 (79)
             82 LOAD_CONST              15 (86)
             85 LOAD_CONST              15 (86)
             88 LOAD_CONST              16 (87)
             91 BUILD_LIST              15
             94 STORE_NAME               6 (SOLUCE)

 19          97 BUILD_LIST               0
            100 STORE_NAME               7 (KEYOUT)

 22         103 SETUP_LOOP              75 (to 181)
            106 LOAD_NAME                3 (PASS)
            109 GET_ITER
        >>  110 FOR_ITER                67 (to 180)
            113 STORE_NAME               8 (X)

 23         116 LOAD_NAME                7 (KEYOUT)
            119 LOAD_ATTR                9 (append)
            122 LOAD_NAME               10 (ord)
            125 LOAD_NAME                8 (X)
            128 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            131 LOAD_NAME                5 (I)
            134 BINARY_ADD
            135 LOAD_NAME               10 (ord)
            138 LOAD_NAME                4 (KEY)
            141 LOAD_NAME                5 (I)
            144 BINARY_SUBSCR
            145 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            148 BINARY_XOR
            149 LOAD_CONST              17 (255)
            152 BINARY_MODULO
            153 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            156 POP_TOP

 24         157 LOAD_NAME                5 (I)
            160 LOAD_CONST              18 (1)
            163 BINARY_ADD
            164 LOAD_NAME               11 (len)
            167 LOAD_NAME                4 (KEY)
            170 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            173 BINARY_MODULO
            174 STORE_NAME               5 (I)
            177 JUMP_ABSOLUTE          110
        >>  180 POP_BLOCK

 30     >>  181 LOAD_NAME                6 (SOLUCE)
            184 LOAD_NAME                7 (KEYOUT)
            187 COMPARE_OP               2 (==)
            190 POP_JUMP_IF_FALSE      206

 31         193 LOAD_NAME                1 (print)
            196 LOAD_CONST              19 ('You Win')
            199 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            202 POP_TOP
            203 JUMP_ABSOLUTE          219

 33     >>  206 LOAD_NAME                1 (print)
            209 LOAD_CONST              20 ('Try Again !')
            212 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            215 POP_TOP
            216 JUMP_FORWARD             0 (to 219)
        >>  219 LOAD_CONST              21 (None)
            222 RETURN_VALUE

On constate que le bytecode Python produit par l’interpréteur de référence CPython est :

• simple et lisible
• documenté
• un bytecode pour stack machine

Si l’on ajoute à cela le fait que le script à l’origine de ce bytecode est court, alors il est simple de faire une décompilation à la main, à partir du bytecode, qui nous permet de retrouver le script suivant :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#!/usr/bin/env python3

if __name__ == '__main__':
    print('Welcome to the RootMe python crackme')
    PASS = input('Enter the Flag: ')
    KEY = 'I know, you love decrypting Byte Code !'
    I = 5
    SOLUCE = [57, 73, 79, 16, 18, 26, 74, 50, 13, 38, 13, 79, 86, 86, 87]
    KEYOUT = []
    for X in PASS:
        KEYOUT.append(ord(X) + I ^ ord(KEY[I]) % 255)
        I = I + 1 % len(KEY)
    if SOLUCE == KEYOUT:
        print('You Win')
    else:
        print('Try Again !')

Maintenant que l’on connaît le résultat à obtenir et comment la chaîne en entrée est transformée, il nous suffit d’appliquer la transformation inverse (et ici la transformation est simple à inverser) sur le résultat attendu (SOLUCE) afin d’obtenir ce que nous cherchons(PASS). Pour ce faire, j’ai fait un petit script Ruby :

1
2
3
4
5
6
7

#!/usr/bin/env ruby

SOLUCE = [57, 73, 79, 16, 18, 26, 74, 50, 13, 38, 13, 79, 86, 86, 87]
KEY = 'I know, you love decrypting Byte Code !'.each_char.map(&:ord).to_a
I = 5
psw = SOLUCE.zip(KEY[I..-1]).each_with_index.map { |(x, k), i| (x^k) - (i+I) }
puts(psw.map(&:chr).join)

Et il nous donne :

1
2

% ./breakit.rb
I_hate_RUBY_!!!

Si j’avais su ^^
Bon allez, testons cela :

1
2
3
4

% ./crackme.py
Welcome to the RootMe python crackme
Enter the Flag: I_hate_RUBY_!!!
You Win

Gagné !
Voilà, ce crackme un peu original est terminé. Il était relativement simple, mais il aura fallu quelques recherches pour en venir à bout. En tout cas, ce fut instructif.

Le crackme étudié dans cet article provient d’ici.

Quatrième crackme, et cette fois nous allons rencontrer notre premier mécanisme anti-débogueur.

Nous avons donc à faire à un exécutable statique avec un strings de 2069 lignes qui ne contient pas de mot de passe (cette fois j’ai vérifié ^^‘)

Ok, sortons le débogueur (comme pour le crackme 2, sauf que cette fois c’est justifié :-P). Mais avant cela, voyons d’abord une exécution normale :

1
2
3
4
5
6
7

############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

Password : AAAAAAAA

Wrong password.

Maintenant, avec notre ami GDB :

1
2
3
4

(gdb) r
Starting program: /home/slaperche/Téléchargements/crackme/ch3.bin
Debugger detecté ... Exit
[Inferior 1 (process 5244) exited with code 01]

Hoho, voyez-vous ça ? Monsieur n’aime pas être surveillé. Bon, on va y aller un peu plus doucement cette fois :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

(gdb) b main
Breakpoint 1 at 0x80483fe
(gdb) r
Starting program: /home/slaperche/Téléchargements/crackme/ch3.bin

Breakpoint 1, 0x080483fe in main ()
(gdb) disass
Dump of assembler code for function main:
   0x080483f0 <+0>:     lea    0x4(%esp),%ecx
   0x080483f4 <+4>:     and    $0xfffffff0,%esp
   0x080483f7 <+7>:     pushl  -0x4(%ecx)
   0x080483fa <+10>:    push   %ebp
   0x080483fb <+11>:    mov    %esp,%ebp
   0x080483fd <+13>:    push   %ecx
=> 0x080483fe <+14>:    sub    $0x14,%esp
   0x08048401 <+17>:    movl   $0x80c2888,-0xc(%ebp)
   0x08048408 <+24>:    push   $0x0
   0x0804840a <+26>:    push   $0x1
   0x0804840c <+28>:    push   $0x0
   0x0804840e <+30>:    push   $0x0
   0x08048410 <+32>:    call   0x8058a70 <ptrace>
   0x08048415 <+37>:    add    $0x10,%esp
   0x08048418 <+40>:    test   %eax,%eax
   0x0804841a <+42>:    jns    0x8048436 <main+70>
   0x0804841c <+44>:    sub    $0xc,%esp
   0x0804841f <+47>:    push   $0x80c2894
   0x08048424 <+52>:    call   0x80492d0 <puts>
   0x08048429 <+57>:    add    $0x10,%esp
   0x0804842c <+60>:    mov    $0x1,%eax
   0x08048431 <+65>:    jmp    0x80484f9 <main+265>
   0x08048436 <+70>:    sub    $0xc,%esp
   0x08048439 <+73>:    push   $0x80c28b0
   0x0804843e <+78>:    call   0x80492d0 <puts>
   0x08048443 <+83>:    add    $0x10,%esp
   0x08048446 <+86>:    sub    $0xc,%esp
   0x08048449 <+89>:    push   $0x80c28f0
   0x0804844e <+94>:    call   0x80492d0 <puts>
   0x08048453 <+99>:    add    $0x10,%esp
   0x08048456 <+102>:   sub    $0xc,%esp
   0x08048459 <+105>:   push   $0x80c2930
   0x0804845e <+110>:   call   0x80492d0 <puts>
   0x08048463 <+115>:   add    $0x10,%esp
   0x08048466 <+118>:   mov    $0x80c296e,%eax
   0x0804846b <+123>:   sub    $0xc,%esp
   0x0804846e <+126>:   push   %eax
   0x0804846f <+127>:   call   0x8048f60 <printf>
   0x08048474 <+132>:   add    $0x10,%esp
   0x08048477 <+135>:   mov    0x80e549c,%eax
   0x0804847c <+140>:   sub    $0x4,%esp
   0x0804847f <+143>:   push   %eax
   0x08048480 <+144>:   push   $0x9
   0x08048482 <+146>:   lea    -0x16(%ebp),%eax
   0x08048485 <+149>:   push   %eax
   0x08048486 <+150>:   call   0x8048f90 <fgets>
   0x0804848b <+155>:   add    $0x10,%esp
   0x0804848e <+158>:   lea    0x8048497,%eax
   0x08048494 <+164>:   inc    %eax
   0x08048495 <+165>:   jmp    *%eax
   0x08048497 <+167>:   mov    $0x8bea558a,%eax
   0x0804849c <+172>:   inc    %ebp
   0x0804849d <+173>:   hlt
   0x0804849e <+174>:   add    $0x4,%eax
   0x080484a1 <+177>:   mov    (%eax),%al
   0x080484a3 <+179>:   cmp    %al,%dl
   0x080484a5 <+181>:   jne    0x80484e4 <main+244>
   0x080484a7 <+183>:   mov    -0x15(%ebp),%dl
   0x080484aa <+186>:   mov    -0xc(%ebp),%eax
   0x080484ad <+189>:   add    $0x5,%eax
   0x080484b0 <+192>:   mov    (%eax),%al
   0x080484b2 <+194>:   cmp    %al,%dl
   0x080484b4 <+196>:   jne    0x80484e4 <main+244>
   0x080484b6 <+198>:   mov    -0x14(%ebp),%dl
   0x080484b9 <+201>:   mov    -0xc(%ebp),%eax
   0x080484bc <+204>:   inc    %eax
   0x080484bd <+205>:   mov    (%eax),%al
   0x080484bf <+207>:   cmp    %al,%dl
   0x080484c1 <+209>:   jne    0x80484e4 <main+244>
   0x080484c3 <+211>:   mov    -0x13(%ebp),%dl
   0x080484c6 <+214>:   mov    -0xc(%ebp),%eax
   0x080484c9 <+217>:   add    $0xa,%eax
   0x080484cc <+220>:   mov    (%eax),%al
   0x080484ce <+222>:   cmp    %al,%dl
   0x080484d0 <+224>:   jne    0x80484e4 <main+244>
   0x080484d2 <+226>:   sub    $0xc,%esp
   0x080484d5 <+229>:   push   $0x80c297a
   0x080484da <+234>:   call   0x80492d0 <puts>
   0x080484df <+239>:   add    $0x10,%esp
   0x080484e2 <+242>:   jmp    0x80484f4 <main+260>
   0x080484e4 <+244>:   sub    $0xc,%esp
   0x080484e7 <+247>:   push   $0x80c298e
   0x080484ec <+252>:   call   0x80492d0 <puts>
   0x080484f1 <+257>:   add    $0x10,%esp
   0x080484f4 <+260>:   mov    $0x0,%eax
   0x080484f9 <+265>:   mov    -0x4(%ebp),%ecx
   0x080484fc <+268>:   leave
   0x080484fd <+269>:   lea    -0x4(%ecx),%esp
   0x08048500 <+272>:   ret
End of assembler dump.

Tiens, tiens, mais que vois-je ? Un appel à ptrace à l’adresse 0x08048410. Il faut savoir que, sous Linux du moins, ptrace est l’appel système à la base des débogueurs. Il permet de mettre en pause un programme, de faire du pas à pas, de lire et écrire sa mémoire et ses registres. Il permet également de détecter si un programme est sous la surveillance de ptrace (et donc, potentiellement sour la surveillance d’un débogueur). Et c’est ce qui est fait ici. Le code :

1
2
3
4
5

   0x08048408 <+24>:    push   $0x0
   0x0804840a <+26>:    push   $0x1
   0x0804840c <+28>:    push   $0x0
   0x0804840e <+30>:    push   $0x0
   0x08048410 <+32>:    call   0x8058a70 <ptrace>

correspond à :

1

ptrace(PTRACE_TRACEME, 0, NULL, NULL);

Qui permet de savoir si le processus courant est sous surveillance.

Maintenant que l’on sait comment le binaire se défend, nous allons pouvoir contourner cette protection. Pour cela, nous pouvons placer un point d’arrêt sur l’instruction qui teste la valeur de retour de ptrace et la changer (sachant que l’appel renvoi -1 si le processus est tracé et 0 si ce n’est pas le cas) avant de continuer l’exécution.

1
2
3
4
5
6
7

(gdb) b *0x08048418
Breakpoint 2 at 0x8048418
(gdb) c
Continuing.

Breakpoint 2, 0x08048418 in main ()
(gdb) set $eax = 0

Avant de continuer, regardons le code de plus près. Bon déjà, il n’y a pas d’appel à strcmp. Cependant, en examinant le code avec attention on remarque cette partie :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

   0x0804849e <+174>:   add    $0x4,%eax
   0x080484a1 <+177>:   mov    (%eax),%al
   0x080484a3 <+179>:   cmp    %al,%dl
   0x080484a5 <+181>:   jne    0x80484e4 <main+244>
   0x080484a7 <+183>:   mov    -0x15(%ebp),%dl
   0x080484aa <+186>:   mov    -0xc(%ebp),%eax
   0x080484ad <+189>:   add    $0x5,%eax
   0x080484b0 <+192>:   mov    (%eax),%al
   0x080484b2 <+194>:   cmp    %al,%dl
   0x080484b4 <+196>:   jne    0x80484e4 <main+244>
   0x080484b6 <+198>:   mov    -0x14(%ebp),%dl
   0x080484b9 <+201>:   mov    -0xc(%ebp),%eax
   0x080484bc <+204>:   inc    %eax
   0x080484bd <+205>:   mov    (%eax),%al
   0x080484bf <+207>:   cmp    %al,%dl
   0x080484c1 <+209>:   jne    0x80484e4 <main+244>
   0x080484c3 <+211>:   mov    -0x13(%ebp),%dl
   0x080484c6 <+214>:   mov    -0xc(%ebp),%eax
   0x080484c9 <+217>:   add    $0xa,%eax
   0x080484cc <+220>:   mov    (%eax),%al
   0x080484ce <+222>:   cmp    %al,%dl
   0x080484d0 <+224>:   jne    0x80484e4 <main+244>

Tiens tiens, on dirait bien qu’il y a un pattern ici :

• on charge un octet dans dl
• on charge une valeur dans eax
• on fait une opération arithmétique sur eax (add ou inc)
• on ramène eax sur un octet.
• on compare al avec dl
• on saute à l’adresse 0x80484e4 si la comparaison précédente génère un résultat différent de 0 (ce qui signifie que les deux opérandes étaient différents).

Cela ressemble étrangement à une boucle (boucle déroulée certes, mais boucle quand même) pour comparer deux chaînes de caractères. Et comme ce pattern se répète quatre fois, on pourrait émettre l’hypothèse que le mot de passe recherché a une longueur de 4 caractères.

Vérifions nos hypothèses en examinant les valeurs de al et dl à chaque cmp. Commençons par poser un point d’arrêt sur le premier cmp.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(gdb) b *0x080484a3
Breakpoint 3 at 0x80484a3
(gdb) c
Continuing.
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

Password : AAAA

Breakpoint 3, 0x080484a3 in main ()
(gdb) p (char)$al
$1 = 101 'e'
(gdb) p (char)$dl
$2 = 65 'A'

Ok, dl semble contenir notre chaîne (on reconnaît notre A), c’est donc al qui va contenir les caractères du mot de passe à trouver (le premier caractère du mot de passe est donc e).

Bien, maintenant que l’on sait quel registre surveiller, continuons avec les autres cmp. Mais avant cela, il va falloir bidouiller un peu. Et oui, le cmp ne va pas produire le résultat attendu et la prochaine instruction va nous faire sauter (ce qui va nous empêcher d’analyser les autres cmp). La prochaine instruction est un jne ce qui signifie Jump if Not Equal, qui est le parfait équivalent de l’instruction jnz (qui signifie Jump if Not Zero). Or le second nom (jnz) nous met la puce à l’oreille : cette instruction se base sur la valeur du flag z. Pour éviter le saut, il va donc falloir mettre ce flag à 1 après l’instruction cmp.
Allons-y :

1
2
3
4
5
6
7

(gdb) ni
0x080484a5 in main ()
(gdb) p $eflags
$3 = [ CF AF SF IF ]
(gdb) set $eflags = $eflags | 64
(gdb) p $eflags
$4 = [ CF AF ZF SF IF ]

Et voilà, le flag z est positionné (il y a peut-être une syntaxe plus simple pour faire ça, mais je n’ai pas trouvé). D’où sort le 64 ? Et bien c’est tout simple : d’après cette page, le flag z correspond au bit 6, et comme chacun sait 2⁶ = 64. S’en suit un petit OU bit à bit pour positionner le flag voulu. Et voilà le travail.

Allez, continuons et découvrons ce fichu mot de passe :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(gdb) b *0x080484b2
Breakpoint 4 at 0x80484b2
(gdb) c
Continuing.

Breakpoint 4, 0x080484b2 in main ()
(gdb) p (char)$al
$5 = 97 'a'
(gdb) ni
0x080484b4 in main ()
(gdb) set $eflags = $eflags | 64
(gdb) b *0x080484bf
Breakpoint 5 at 0x80484bf
(gdb) c
Continuing.

Breakpoint 5, 0x080484bf in main ()
(gdb) p (char)$al
$6 = 115 's'
(gdb) ni
0x080484c1 in main ()
(gdb) set $eflags = $eflags | 64
(gdb) b *0x080484ce
Breakpoint 6 at 0x80484ce
(gdb) c
Continuing.

Breakpoint 6, 0x080484ce in main ()
(gdb) p (char)$al
$7 = 121 'y'

Ok, le mot de passe serait donc easy.

Voyons voir :

1
2
3
4
5
6
7
8

% ./ch3.bin
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

Password : easy

Good password !!!

Gagné !
Ça commence à devenir intéressant :-)

Le crackme étudié dans cet article provient d’ici.

Avec ce troisième crackme, on reste dans du très simple mais ça va nous permettre de voir une nouvelle approche lorsque l’on veut faire de la rétroingénierie sur des exécutables dynamiques.

Bon, déjà voyons à quoi nous avons à faire.

1
2

% ./crackme
(*) -Syntaxe: ./crackme03 [password]

Ok, celui-ci prend le mot de passe via les arguments de la ligne de commande.

Commençons par le traditionnel strings qui, comme on pouvait s’y attendre, ne nous apprend pas grand-chose.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

% strings crackme
/lib/ld-linux.so.2
__gmon_start__
libc.so.6
_IO_stdin_used
strcpy
exit
puts
__stack_chk_fail
printf
memcpy
malloc
strcmp
__libc_start_main
GLIBC_2.4
GLIBC_2.0
PTRh0
QVhT
libe
_0cG
jc5m
_.5T
[^_]
(*) -Syntaxe: %s [password]
_0cGj35m9V5T3
8CJ0
9H95h3xdh
_Celebration
rification de votre mot de passe..
(!) L'authentification a
chou
 Try again !
'+) Authentification r
ussie...
 U'r root!
 sh 3.0 # password: %s
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan

Il y a bien quelques chaînes qui ressemblent vaguement à un mot de passe, mais aucune ne fonctionne.

1
2
3
4
5
6

% ./crackme _0cGj35m9V5T3
Vérification de votre mot de passe..
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
% ./crackme 9H95h3xdh
Vérification de votre mot de passe..
le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan

Voyons à quel type de binaire nous avons là :

1

crackme03: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.8, not stripped

Hum, intéressant : cet exécutable est lié dynamiquement. Voyons donc ce que nous donne un petit ltrace :

1
2
3
4
5
6
7
8
9
10
11
12
13

% ltrace ./crackme AAAAAAAA
__libc_start_main(0x8048554, 2, 0xbfa5d744, 0x8048840, 0x8048830 <unfinished ...>
malloc(29)                                                                                                     = 0x09a6d008
memcpy(0x09a6d008, "_0cGj35m9V5T3\303\2078CJ0\303\2009H95h3xdh", 31)                                           = 0x09a6d008
memcpy(0xbfa5d60a, "_Celebration", 13)                                                                         = 0xbfa5d60a
strcpy(0xbfa5d66e, "AAAAAAAA")                                                                                 = 0xbfa5d66e
puts("V\303\251rification de votre mot de pa"...Vérification de votre mot de passe..
)                                                              = 38
strcmp("AAAAAAAA", "_0cGjc5m_.5\r\n\303\2078CJ0\303\2009")                                                     = -1
printf("le voie de la sagesse te guidera"...le voie de la sagesse te guidera, tache de trouver le mot de passe petit padawaan
)                                                                  = 84
exit(0  <unfinished ...>
+++ exited (status 0) +++

Hum, c’est très instructif. On voit que le code fait un strcmp contre une chaîne un peu bizarre. Essayons d’utiliser cette chaîne bizarre en tant que mot de passe. Étant donné que la chaîne contient la séquence de caractères de contrôles \r\n, je préfère utiliser Ruby pour passer la chaîne en argument (d’autres solutions étaient bien sûr possible) plutôt que d’essayer de la taper directement dans le shell.

1
2
3
4
5
6

% ./crackme "$(ruby -e 'print("_0cGjc5m_.5\r\n\303\2078CJ0\303\2009")')"
Vérification de votre mot de passe..
'+) Authentification réussie...
 U'r root!

  sh 3.0 # password: liberté!

Gagné !
Le mot de passe est donc liberté!.

Le crackme étudié dans cet article provient d’ici.

Ce second crackme est un peu moins simple que le précédent, mais il est tout de même trivial. En revanche, je me suis compliqué la vie : la solution était en fait bien plus simple que ce que l’on peut penser. Mais au moins, ça me permet de présenter l’usage de GDB ^^

Comme la dernière fois, on va commencer par lancer strings sur notre binaire. Cependant, cette fois le nombre de chaîne de caractères est beaucoup plus important (1506 chaînes). Ayant la flemme de regarder cela en détail (pourtant j’aurai dû, comme vous le verrez par la suite), je décide de passer à autre chose.

Déjà, on peut remarquer (via la commande file ou ldd) que l’exécutable est compilé en mode statique (ce qui explique le grand nombre de chaîne de caractères), ça signifie que l’on peut oublier d’office les bidouilles à base de ltrace et autres LD_PRELOAD (ne vous inquiétez pas, on aura l’occasion de s’amuser avec ça dans d’autres défis).

Partant de ces premières observations, je décide de partir sur GDB. Mais avant cela, voyons une exécution normale :

1
2
3
4
5
6
7

% ./ch2.bin
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

username: foo
Bad username

Ok, il faut donc fournir un nom d’utilisateur avant de pouvoir fournir le mot de passe.

Maintenant, passons à GDB. Première chose à faire : placer un point d’arrêt sur la fonction main, puis regarder le code assembleur.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

(gdb) b main
Breakpoint 1 at 0x8048317
(gdb) r
Starting program: ch2.bin

Breakpoint 1, 0x08048317 in main ()
(gdb) disass
Dump of assembler code for function main:
   0x08048309 <+0>:     lea    0x4(%esp),%ecx
   0x0804830d <+4>:     and    $0xfffffff0,%esp
   0x08048310 <+7>:     pushl  -0x4(%ecx)
   0x08048313 <+10>:    push   %ebp
   0x08048314 <+11>:    mov    %esp,%ebp
   0x08048316 <+13>:    push   %ecx
=> 0x08048317 <+14>:    sub    $0x24,%esp
   0x0804831a <+17>:    movl   $0x80a6b19,-0xc(%ebp)
   0x08048321 <+24>:    movl   $0x80a6b1e,-0x10(%ebp)
   0x08048328 <+31>:    movl   $0x80a6b2c,(%esp)
   0x0804832f <+38>:    call   0x8048de0 <puts>
   0x08048334 <+43>:    movl   $0x80a6b6c,(%esp)
   0x0804833b <+50>:    call   0x8048de0 <puts>
   0x08048340 <+55>:    movl   $0x80a6bac,(%esp)
   0x08048347 <+62>:    call   0x8048de0 <puts>
   0x0804834c <+67>:    movl   $0x80a6bea,(%esp)
   0x08048353 <+74>:    call   0x8048db0 <printf>
   0x08048358 <+79>:    mov    -0x8(%ebp),%eax
   0x0804835b <+82>:    mov    %eax,(%esp)
   0x0804835e <+85>:    call   0x804826a <getString>
   0x08048363 <+90>:    mov    %eax,-0x8(%ebp)
   0x08048366 <+93>:    mov    -0xc(%ebp),%eax
   0x08048369 <+96>:    mov    %eax,0x4(%esp)
   0x0804836d <+100>:   mov    -0x8(%ebp),%eax
   0x08048370 <+103>:   mov    %eax,(%esp)
   0x08048373 <+106>:   call   0x80502f0 <strcmp>
   0x08048378 <+111>:   test   %eax,%eax
   0x0804837a <+113>:   jne    0x80483d0 <main+199>
   0x0804837c <+115>:   movl   $0x80a6bf5,(%esp)
   0x08048383 <+122>:   call   0x8048db0 <printf>
   0x08048388 <+127>:   mov    -0x8(%ebp),%eax
   0x0804838b <+130>:   mov    %eax,(%esp)
   0x0804838e <+133>:   call   0x804826a <getString>
   0x08048393 <+138>:   mov    %eax,-0x8(%ebp)
   0x08048396 <+141>:   mov    -0x10(%ebp),%eax
   0x08048399 <+144>:   mov    %eax,0x4(%esp)
   0x0804839d <+148>:   mov    -0x8(%ebp),%eax
   0x080483a0 <+151>:   mov    %eax,(%esp)
   0x080483a3 <+154>:   call   0x80502f0 <strcmp>
   0x080483a8 <+159>:   test   %eax,%eax
   0x080483aa <+161>:   jne    0x80483c2 <main+185>
   0x080483ac <+163>:   movl   $0x80a6c00,0x4(%esp)
   0x080483b4 <+171>:   movl   $0x80a6c0c,(%esp)
   0x080483bb <+178>:   call   0x8048db0 <printf>
   0x080483c0 <+183>:   jmp    0x80483dc <main+211>
   0x080483c2 <+185>:   movl   $0x80a6c52,(%esp)
   0x080483c9 <+192>:   call   0x8048de0 <puts>
   0x080483ce <+197>:   jmp    0x80483dc <main+211>
   0x080483d0 <+199>:   movl   $0x80a6c5f,(%esp)
   0x080483d7 <+206>:   call   0x8048de0 <puts>
   0x080483dc <+211>:   mov    $0x0,%eax
   0x080483e1 <+216>:   add    $0x24,%esp
   0x080483e4 <+219>:   pop    %ecx
   0x080483e5 <+220>:   pop    %ebp
   0x080483e6 <+221>:   lea    -0x4(%ecx),%esp
   0x080483e9 <+224>:   ret
End of assembler dump.

Information intéressante : il y a deux appels à strcmp. Ça pourrait bien correspondre aux vérifications du nom d’utilisateur et du mot de passe. On va donc placer un point d’arrêt sur strcmp afin de pouvoir examiner son code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

(gdb) b *0x80502f0
Breakpoint 2 at 0x80502f0
(gdb) c
Continuing.
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

username: AAAAAAAA

Breakpoint 2, 0x080502f0 in strcmp ()
(gdb) disass
Dump of assembler code for function strcmp:
=> 0x080502f0 <+0>:     push   %ebp
   0x080502f1 <+1>:     xor    %edx,%edx
   0x080502f3 <+3>:     mov    %esp,%ebp
   0x080502f5 <+5>:     push   %esi
   0x080502f6 <+6>:     push   %ebx
   0x080502f7 <+7>:     mov    0x8(%ebp),%esi
   0x080502fa <+10>:    mov    0xc(%ebp),%ebx
   0x080502fd <+13>:    lea    0x0(%esi),%esi
   0x08050300 <+16>:    movzbl (%esi,%edx,1),%eax
   0x08050304 <+20>:    movzbl (%ebx,%edx,1),%ecx
   0x08050308 <+24>:    test   %al,%al
   0x0805030a <+26>:    je     0x8050328 <strcmp+56>
   0x0805030c <+28>:    add    $0x1,%edx
   0x0805030f <+31>:    cmp    %cl,%al
   0x08050311 <+33>:    je     0x8050300 <strcmp+16>
   0x08050313 <+35>:    movzbl %al,%edx
   0x08050316 <+38>:    movzbl %cl,%eax
   0x08050319 <+41>:    sub    %eax,%edx
   0x0805031b <+43>:    mov    %edx,%eax
   0x0805031d <+45>:    pop    %ebx
   0x0805031e <+46>:    pop    %esi
   0x0805031f <+47>:    pop    %ebp
   0x08050320 <+48>:    ret
   0x08050321 <+49>:    lea    0x0(%esi,%eiz,1),%esi
   0x08050328 <+56>:    movzbl %cl,%edx
   0x0805032b <+59>:    neg    %edx
   0x0805032d <+61>:    mov    %edx,%eax
   0x0805032f <+63>:    pop    %ebx
   0x08050330 <+64>:    pop    %esi
   0x08050331 <+65>:    pop    %ebp
   0x08050332 <+66>:    ret
End of assembler dump.

On prend soin d’utiliser une chaîne très facilement reconnaissable en tant que nom d’utilisateur, ça peut être utile par la suite.
En analysant le code on voit que la comparaison (instruction cmp à l’adresse 0x0805030f) se fait sur le contenu des registres cl et al. Ces registres correspondent en fait aux registres 32-bit ecx et eax traités comme des registres 8-bit. Or, on voit que les valeurs de ces registres sont chargées à partir des adresses contenues dans esi (pour eax) et ebx (pour ecx) via des instructions movzbl. Il suffit donc de mettre un point d’arrêt après le chargement des adresses dans esi et ebx afin de pouvoir afficher les chaînes de caractères :

1
2
3
4
5
6
7
8
9
10

(gdb) b *0x08050300
Breakpoint 3 at 0x8050300
(gdb) c
Continuing.

Breakpoint 3, 0x08050300 in strcmp ()
(gdb) p (char*)$esi
$1 = 0x80c8688 "AAAAAAAA"
(gdb) p (char*)$ebx
$2 = 0x80a6b19 "john"

On reconnaît notre chaîne AAAAAAAA dans esi, c’est donc ebx qui contient le nom d’utilisateur. On découvre alors que le nom d’utilisateur est john.

Comme nous avons donné un mauvais mot de passe, le programme va se terminer avant que nous puissions découvrir le mot de passe. Pour éviter cela, nous allons modifier la valeur de retour de strcmp. On commence par ajouter un point d’arrêt juste après le premier appel de strcmp dans main, puis on placera 0 (valeur de retour de strcmp lorsque les deux chaînes sont identiques) dans le registre eax (registre utilisé pour stocker la valeur de retour, ce comportement est défini par la convention d’appel utilisée) avant de continuer l’exécution.

1
2
3
4
5
6
7
8
9
10
11
12

(gdb) b *0x08048378
Breakpoint 4 at 0x8048378
(gdb) c
Continuing.

Breakpoint 4, 0x08048378 in main ()
(gdb) set $eax = 0
(gdb) c
Continuing.
password: BBBBBBBB

Breakpoint 2, 0x080502f0 in strcmp ()

Comme prévu, il nous demande le mot de passe et l’on se retrouve à nouveau dans strcmp. En appliquant le même principe que précédemment on obtient le mot de passe.

1
2
3
4
5
6

(gdb) c
Continuing.

Breakpoint 3, 0x08050300 in strcmp ()
(gdb) p (char*)$ebx
$3 = 0x80a6b1e "the ripper"

Étant maintenant en possession des identifiants, on peut récupérer le code secret :

1
2
3
4
5
6
7
8

% ./ch2.bin
############################################################
##        Bienvennue dans ce challenge de cracking        ##
############################################################

username: john
password: the ripper
Bien joue, vous pouvez valider l'epreuve avec le mot de passe : 987654321 !

Gagné !
Le mot de passe était donc 987654321.

Le mot de la fin

Pour information, tout cela était inutile. En effet, la sortie de strings nous donnait déjà toutes les informations nécessaires (pour peu que l’on prenne le temps de la regarder de plus près) :

1
2
3
4
5
6
7

% strings ch2.bin
[…]
john
the ripper
[…]
987654321
[…]

On voit donc que le nom d’utilisateur et le mot de passe était en clair dans le binaire. Pis encore : le code à obtenir (987654321) est lui aussi en clair dans le binaire. On n’avait même pas besoin de connaître le nom d’utilisateur et le mot de passe pour y accéder.