[CPU] Pipeline

Qu'est-ce qu'un pipeline ?

Le pipeline est une technique implémentée dans un processeur pour optimiser le temps de traitement d'une instruction. En clair il repose sur le principe simple de la chaîne de montage, pour produire plusieurs fois à la suite des objets on peut faire chaque objet d'un coup, un à la suite. Le temps total sera donc le nombre d'objet multiplié par le temps mis pour un seul objet.
Maintenant l'idée est de découper la fabrication de l'objet en plusieurs étapes ou "étages" indépendants, de telle sorte que chaque étage peut fonctionner en même temps que tous les autres et qu'il soit nécessaire de passer par tous les étages inférieurs pour atteindre un étage donné.

Ainsi imaginons un pipeline à 3 étages et 3 objets à concevoir et supposons que le temps mis à chaque étage soit le même : T. L'objet 1 arrive au premier étage du pipeline, pendant ce temps les deux autres objets attendent, une fois l'étape 1 passée, l'objet 1 passe à l'étage 2, libérant ainsi l'étage 1, l'objet 2 est donc placé à l'étage 1, l'objet 3 attend. Ensuite une fois l'étape 2 de l'objet 1 et l'étape 1 de l'objet 2 finies, l'objet 1 passe à l'étage 3, l'objet 2 à l'étage 2 et l'objet 3 à l'étage 1 qui vient d'être libéré. Et ainsi de suite...

Le temps total mis sans pipeline serait par exemple de 3 * 3T soit 9T. Avec pipeline il est seulement de 5T !

L'idée est la même pour le pipeline du CPU, chaque instruction à exécuter est séparée en étages mettant sur ce schéma un cycle d'horloge à être exécutée. Les étapes sont les suivantes le "fetch" (IF pour "Instruction Fetch") qui sépare la commande et les opérandes, le décode (ID pour "Instruction Decode") qui permet de traduire la commande pour la rendre intelligible par les unités du processeur, l'exécution à proprement dit de l'instruction (EX), MEM (Memory) correspond aux opérations post-exécution qui sont exécutées dans la mémoire, par exemple écrire à un certain endroit ou lire une donnée, et enfin le "Write-Back" (WB) finalise l'instruction en mettant à jour les registres avec les résultats.

Ce type de pipeline synchronisé par le front d'horloge du CPU est appelé "pipeline synchrone", il existe un autre type de pipeline appelé "asynchrone" où la mise à jour et les changements d'étages sont effectués via la communication entre les étages.

Le nombre d'étages du pipeline est caractéristique du CPU et est appelé "profondeur du pipeline", la profondeur des pipelines des processeurs modernes est souvent entre 12 et 15 étapes, qui sont des découpages des étapes présentées (fetch, decode..)

Spinlock & Mutex ?

Quelle est la différence entre un mutex et un spinlock ?

Les deux concepts sont quasiment identiques puisque les deux sont des mécanismes de synchronisation.
Quand un thread essaye de lock un mutex, si il réussit, il prend le contrôle de ce mutex et accède aux données partagées, sinon il attend simplement son tour dans une queue.
Le spinlock diffère légèrement : quand un thread essaye de le lock alors qu'il est déjà pris ailleurs, le thread va continuer sans arrêt de réessayer de le lock jusqu'à qu'il en prenne le contrôle, d'où l'idée de "spin" car le thread recommence tout le temps. Un tel mécanisme est très consommateur de cycles de CPU et est généralement inutile sur un système mono-processeur, mais peuvent s'avérer rentable sur des systèmes multi-processeurs.

Cependant il existe également des mutex hybrides, dans les systèmes modernes, si un thread essaye de lock ce mutex et qu'il n'y arrive pas, il ne va pas se mettre en pause et attendre (comme le ferait un thread avec des mutex classiques) mais va spinlock pendant un court instant, et si après cela le mutex n'est toujours pas unlock par le thread, alors il est mis en attente.

[Os] Comment reboot un ordinateur ?

Une question qui peut revenir pour ceux qui s'intéressent au développement des systèmes d'exploitation, à l'assembleur ou qui veulent simplement comprendre le fonctionnement d'un ordinateur.

D'un point de vue de programmeur, il existe une manière décrite dans le manuel d'intel pour les processeurs x86 pour redémarrer l'ordinateur, il faut pour cela générer une "triple fault".
Une triple fault intervient lorsqu'une interruption est générée et qu'une routine (ISR) n'est pas trouvée pour cette interruption. Pour cela il "suffit" de provoquer en toute conscience l'erreur en chargeant en mémoire une table de descripteurs d'interruption (IDT) vide et en générant manuellement une interrupt en appelant "int", l'interruption échoue et le gestionnaire de faute échoue aussi et le CPU provoque un redémarrage.

Cependant en réalité pour redémarrer, étant donné l'implémentation de l'ACPI (Advanced configuration and power interface) pour gérer l'alimentation, les systèmes d'exploitation envoient simplement une instruction de reboot au gestionnaire, la carte-mère se charge de reboot tous les composants et n'est jamais elle-même éteinte.

Malware et mutex

Les mutex sont un mécanisme de protection de données partagées, si deux threads concurrents essayaient d'accéder en même temps (avec le parallélisme d'exécution) à une même donnée, alors la donnée risque d'être corrompue, et le code deviendra buggé.
Pour cela on utilise un mutex afin de "synchroniser" l'accès aux données par les threads, si le thread A veut lire une valeur à une certaine adresse mémoire, il va "vérouiller" (lock) le mutex correspondant, empêchant tout autre thread B tentant de le vérouiller à son tour de continuer son exécution, faire son affaire avec la valeur, et libérer le mutex, afin qu'un éventuel thread B concurrent puisse prendre le contrôle du mutex et utiliser la donnée.

Voilà pour la théorie de programmation concurrente, les malwares multithreadés utilisent également ce système pour éviter d'avoir des problèmes de synchronisation, cependant en plus de cela, les mutex sont utilisés par ces malwares pour éviter d'infecter deux fois la même cible.
En effet le logiciel va au démarrage vérifier si un mutex global est présent sur le système (il identifie le mutex avec un nom spécial), si c'est le cas le programme malveillant s'interrompt car la machine est déjà infectée, sinon il crée ce mutex et continue son infection.

Il est possible d'analyser les mutex (aussi appelés "mutant") présents sur le système afin de vérifier si une machine est infectée ou non par une menace donnée.

Evaluer une intégrale numériquement

Il peut parfois se révéler utile ou nécessaire de calculer une intégrale (qu'on suppose bien définie) sur un segment [a;b] numériquement dans un programme.

On peut en premier lieu évaluer l'intégrale au moyen de la méthode des rectangles, c'est à dire en sommant simplement les f(x)*dx pour des valeur  :

for(i=a; i < b; i += dx)
{
    sum += f(i)*dx;
}

Il existe également des méthodes pour évaluer une intégrale numériquement, une célèbre étant la méthode de Simpson qui utilise l'interpolation polynomiale de Lagrange pour approximer la courbe et intégrer le polynôme obtenu permet d'obtenir une bonne évaluation de l'intégrale de départ.

Le code cave et l'infection PE

A propos de PE:

Le format "Portable Executable" de windows est conçu pour être pratique et permettre d'organiser un fichier exécutable afin de contenir diverses informations pour son lancement et quelques ressources (comme une image ou un autre binaire). L'organisation interne du format est très documentée et le fichier en lui même et ses différentes sections peuvent être vues comme des répertoires dans lesquelles sont rangés plusieurs choses, les premiers octets du fichier sont des headers. L'en-tête du PE contient une en-tête DOS, une en-tête Nt et une en-tête pour les différentes sections. On trouve ensuite les sections en elles-mêmes.

Les structures des en-têtes sont documentées sur le site de Microsoft, et un des header principaux : l'Image Optional Header (qui n'a rien d'optionnel, doc)  contient des champs primordiaux, dont la taille de l'image, l'adresse relative du point d'entrée, l'adresse de la section code, la checksum, etc.
On peut évidemment modifier ces informations en écrivant les bons octets aux bons endroits du fichier.

Code Cave ?

La section code contient le code à proprement parler de l'exécutable sous forme d'opcode, à partir duquel on peut déduire l'ASM. Une partie de la section, à la fin du vrai code est remplie de 0 jusqu'au début de la section suivante, cet espace ne sert normalement qu'à aligner les données, mais le but de l'infection d'un fichier PE par le code-cave est de réquisitionner cet espace, d'y écrire un shellcode totalement arbitraire réalisant diverses opérations. Il faut ensuite rediriger le point d'entrée de l'image (le membre AddressOfEntryPoint de la structure IMAGE_OPTIONAL_HEADER) vers l'adresse de base du shellcode, de cette manière lorsque que l'exécutable sera lancé, le code sera exécuté en premier, il convient alors de terminer le shellcode par un jmp (0xE9) vers l'adresse originale du point d'entrée afin que le programme démarre normalement alors que notre code a été exécuté avant.

Quel intérêt de cette méthode ?

L'infection du PE au moyen d'un code cave a ceci de bien  qu'elle préserve la taille du fichier, elle ne crée aucune section supplémentaire et est à ce titre beaucoup moins détectable qu'une infection rajoutant une section à la fin du PE en lui donnant un flag exécutable, ou en redirigeant le point d'entrée vers des endroits suspects (typiquement avant la première section). Il existe d'autres techniques plus sophistiquées comme la fragmentation du shellcode et l'utilisation de plusieurs caves, qui necéssite un programme d'infection plus compliqué et un "loader" injecté dans le code pour rassembler les pièces du shellcode...

(P.S : on parle ici de code-cave dans le cas d'une infection PE, le terme code-cave est aussi utilisé dans le même esprit pour une injection de code dans un thread, où la technique est la même et consiste à injecter le shellcode dans un endroit libre à distance.)

Interpolation linéaire et lagrangienne

  Interpolation linéaire et lagrangienne réalisée en C, avec les bibliothèques SDL et OpenGL.

En bleu sont représentés les points initiaux à relier, en vert le résultat de l'interpolation polynomiale de Lagrange, en rouge l'interpolation linéaire par segment, cette dernière méthode est très simple et consiste à prendre les points deux à deux et à obtenir l'équation de la droite qui passe par ces deux points. La fonction affine obtenue est ensuite tracée sur le segment [x1, x2] et on passe aux points [x2, x3] en recommençant l'opération jusqu'à ce que tous les points aient été reliés.

L'interpolation polynomiale lagrangienne permet d'obtenir à partir des coordonnées directement l'équation de la courbe les reliant, elle fait appel aux polynômes de Lagrange, et l'équation de la courbe est donnée dans cet article : Interpolation lagrangienne

L'algorithme pour calculer le polynôme en X donne en C :

float lagrange(float X, float *x, float *y, int n)
{
    int i,j;
    float poly = 0;
    float prod = 1;
    for(j = 0; j < n; ++j) {
        for(i = 0; i < n; ++i) {
            if(i==j)
                continue;
            prod *= (X - x[i])/(x[j] - x[i]);
        }
        poly += y[j]*prod;
        prod = 1;
    }
    return poly;
}