# Fragmentation (informatique)

En informatique, la fragmentation peut désigner plusieurs concepts :
* la fragmentation d'un disque dur,
* la fragmentation de la mémoire vive,
* la fragmentation des paquets dans les réseaux informatiques à commutation de paquets.

## La fragmentation d'un disque dur
### Principe de fragmentation

Le disque dur d'un ordinateur est divisé en secteurs et le système d'exploitation les rassemble pour former des blocs (clusters en anglais). Ainsi, un fichier est contenu sur un nombre entier de blocs : le dernier bloc n'est pas toujours entièrement rempli de données.
Chaque fichier utilise donc plusieurs blocs. Si les blocs contenant le fichier sont contigus, celui-ci n'est pas fragmenté. Toutefois, en pratique, les blocs d'un fichier sont généralement éparpillés par groupes, d'où la fragmentation du fichier.

### Analogie

Reprenons l'exemple de Roberto Di Cosmo, en simplifiant.
Assimilons le disque dur à une grande armoire à tiroirs, tous de même taille, dans laquelle on rangerait des dossiers.
Au départ, tous les tiroirs sont vides, et la personne peut remplir les premiers tiroirs sans problème. Des dossiers sont retirés, ce qui amène des trous dans la rangée des tiroirs. Un problème se pose alors lorsqu'un dossier est trop grand pour rentrer intégralement dans un des emplacements vides. Le dossier est alors séparé en plusieurs morceaux puis réparti dans des cases vides.
Maintenant, si la personne doit aller chercher ce dossier, elle doit aller chercher les différentes parties du dossier à des endroits différents, ce qui prend plus de temps que si l'intégralité du dossier était stockée au même endroit. Pour y remédier, il suffit que, régulièrement, quelqu'un s'occupe de réorganiser toute l'armoire en rassemblant les éléments de chaque dossier, ce qu'on appelle la défragmentation.
Ce mode de fonctionnement est actuellement utilisé par les ordinateurs fonctionnant sous Microsoft Windows, plus précisément, c'est le mode de fonctionnement des systèmes de fichiers NTFS.

### La fragmentation selon le système d'exploitation
#### Le cas des dérivés d'UNIX

Tous les systèmes UNIX ont la même gestion de la fragmentation. Le noyau calcule le nombre de blocs nécessaires au stockage de chaque fichier sur le disque dur. Si un tel nombre de clusters libres contigus est trouvé sur le disque, il stocke le fichier sur ces clusters, contigus, et le fichier n'est pas fragmenté. S'il ne trouve pas assez de clusters libres contigus, il scinde le fichier en plusieurs groupes de clusters et éparpille ces groupes sur le disque dur : il tente de minimiser le nombre de groupes et par conséquent remplit les plus grands espaces de clusters vides contigus en premier.

#### Le cas de Microsoft Windows

Le noyau NT essaie de combler les trous dans le sens où il fragmente le fichier pour ne pas laisser au début du disque, des zones avec des clusters libres.

### Cas dans lesquels survient la fragmentation

Dans les systèmes Unix, la fragmentation fait suite à un espace disque trop faible.
Pour Microsoft Windows, la fragmentation trouve sa source dans les multiples suppressions, modifications, copies de fichiers sur le disque dur, qui favorisent l'apparition de zones de clusters libres, et par conséquent la fragmentation. Elle est donc fréquente sur les Systemes Windows car il est courant pour un utilisateur de manipuler des fichiers.

### Atteinte sur les performances

Si la fragmentation est si problématique, c'est parce qu'elle engendre des problèmes au niveau physique.
Lorsqu'un fichier n'est pas fragmenté, la tête de lecture du disque dur n'a pas besoin de se déplacer, ou très peu, puisque les clusters sont les uns à la suite des autres.
À l'inverse, si le fichier est fragmenté, la tête de lecture va faire de multiples aller-retours pour lire chacun des groupes de clusters : se déplacer prend du temps, donc plus le fichier est fragmenté, plus le temps pour accéder à son contenu est élevé.

## Fragmentation de la mémoire vive

La fragmentation est un problème qui survient quand on dispose d'une partie libre de la mémoire mais qu'on ne peut pas allouer à un programme.
On distingue deux types de fragmentation:
-Fragmentation interne : elle a lieu lorsqu'une partie d'une page est libre et la taille de la dernière partie du processus est inférieure à la taille d'une page.
-Fragmentation externe : elle survient lorsqu'on dispose d'une partie libre de la mémoire dont la taille est inférieure à la taille du processus.
Exemples de techniques pour réduire la fragmentation :
L'architecture interne de malloc a été conçue pour réduire la fragmentation de la mémoire vive. Il y a plusieurs pools de tampon, chaque pool correspond à une taille de tampon différente. Il y aura un pool pour les tampons de moins de 100 octets, un autre pour les tampons de 100 à 1 000 octets.

## Fragmentation de paquets
### Définition

La fragmentation est une fonctionnalité proposée par les deux versions du protocole Internet (IPv4 et IPv6) permettant de diviser un paquet initial en plus petits morceaux (datagramme) afin que les morceaux résultants puissent être transmis par une liaison avec une unité de transmission maximale plus petite que la taille du paquet original.

### Avec IPv4

Dans IPv4, le datagramme IP est fragmenté en plus petites parties appelés fragments. Chaque fragment est ensuite encapsulé dans une trame de couche de liaison séparée et envoyé ensuite sur la liaison sortante. Comme le réassemblage d'un paquet dans un routeur créerait de nombreux problèmes, les fragments sont assemblés grâce à l'hôte récepteur. L'hôte doit déterminer si les fragments sont originaux ou s'ils sont extraits d'un plus grand. Pour réassembler ces fragments, l'en-tête du datagramme IP contient une identification, un drapeau et des champs de décalage de fragmentation.
Lorsqu'un routeur a besoin de fragmenter, chaque fragment est marquée avec l'adresse source, l'adresse de destination et le numéro d'identification. Lorsque la destination reçoit une série envoyé par même hôte, elle peut examiner les numéros d'identification pour déterminer lesquels sont en fait des fragments. Comme l'IP est un service peu fiable, un ou plusieurs des fragments peuvent ne jamais arriver à destination. Ainsi, pour que l'hôte de destination soit sûr d'avoir reçu le dernier fragment d'origine, le dernier fragment a un bit indicateur réglé à 0, alors que tous les autres fragments ont ce bit indicateur réglé à 1. De plus, pour que l'hôte de destination puisse déterminer si un fragment est manquant et réassembler les paquets, le champ de décalage est utilisé pour spécifier où le fragment se situe dans le datagramme IP d'origine.

### Avec IPv6

Contrairement à IPv4, IPv6 ne permet pas la fragmentation au niveau des routeurs intermédiaires car il s'agit d'une opération qui prend du temps. La fragmentation et le réassemblage ne sont autorisés que pour la source et la destination. Si une route reçoit un datagramme IPv6 trop important pour être transmis. Le routeur laisse simplement tomber le paquet et envoie un message ICMP "PACKET TOO BIG" à l'expéditeur. L'expéditeur renverra les données en utilisant une taille de datagramme IP plus petite.

### Faille

Plus connu sous le nom de Teardrop Attack, Bonkou encore Boink, cette attaque utilise une faille propre à certaines piles TCP/IP. Cette vulnérabilité concerne la gestion de la fragmentation IP. Ce problème apparaît lorsque la pile reçoit le deuxième fragment d’un paquet TCP contenant comme donnée le premier fragment. La pile TCP/IP peut s’avérer incapable de gérer cette exception et le reste du traﬁc. Cette faille est très connue sur les piles de Windows 95 et 98.