Mécanismes d'allocation de Go

Lorsque j'ai essayé pour la première fois de comprendre le fonctionnement des outils d'allocation de mémoire dans Go, ce que je voulais gérer semblait être une mystérieuse boîte noire. Comme pour toute autre technologie, la chose la plus importante ici est cachée derrière de nombreuses couches d'abstractions, à travers lesquelles vous devez passer pour comprendre quelque chose.



L'auteur du matériel, dont nous publions la traduction, a décidé d'aller au fond des moyens d'allocation de mémoire dans Go et d'en parler.

Mémoire physique et virtuelle

Tous les moyens d'allocation de mémoire doivent fonctionner avec l'espace d'adressage de la mémoire virtuelle, qui est contrôlé par le système d'exploitation. Voyons comment fonctionne la mémoire, en commençant au niveau le plus bas - avec les cellules de mémoire.
Voici comment imaginer une cellule RAM.


Disposition des cellules de mémoire

Si, très simplifié, imaginez une cellule mémoire et ce qui l'entoure, alors nous obtenons ce qui suit:

1. La ligne d'adresse (le transistor agit comme un interrupteur) est ce qui donne accès au condensateur (ligne de données).
2. Lorsqu'un signal apparaît dans la ligne d'adresse (ligne rouge), la ligne de données vous permet d'écrire des données dans la cellule mémoire, c'est-à-dire de charger le condensateur, ce qui permet d'y stocker une valeur logique correspondant à 1.
3. Lorsqu'il n'y a pas de signal dans la ligne d'adresse (ligne verte), le condensateur est isolé et sa charge ne change pas. Pour écrire dans la cellule 0, vous devez sélectionner son adresse et soumettre un 0 logique via la ligne de données, c'est-à-dire connecter la ligne de données avec un moins, déchargeant ainsi le condensateur.
4. Lorsque le processeur doit lire la valeur de la mémoire, le signal est envoyé le long de la ligne d'adresse (le commutateur se ferme). Si le condensateur est chargé, le signal passe par la ligne de données (1 est lu), sinon le signal ne passe pas par la ligne de données (0 est lu).

Le schéma d'interaction de la mémoire physique et du processeur

Le bus de données est responsable du transport des données entre le processeur et la mémoire physique.

Parlons maintenant de la ligne d'adresse et des octets adressables.


Lignes d'adresse de bus entre le processeur et la mémoire physique

1. Chaque octet dans la RAM se voit attribuer un identifiant numérique unique (adresse). Il est à noter que le nombre d'octets physiques présents dans la mémoire n'est pas égal au nombre de lignes d'adresse.
2. Chaque ligne d'adresse peut spécifier une valeur de 1 bit, elle indique donc un bit dans l'adresse d'un certain octet.
3. Notre circuit dispose de 32 lignes d'adresse. Par conséquent, chaque octet adressable utilise un nombre 32 bits comme adresse. [00000000000000000000000000000000] - l'adresse mémoire la plus basse. [1111111111111111111111111111111111] - l'adresse mémoire la plus élevée.
4. Étant donné que chaque octet a une adresse 32 bits, notre espace d'adressage se compose de 2 ³² octets adressables (4 Go).

Il en résulte que le nombre d'octets adressables dépend du nombre total de lignes d'adresse. Par exemple, s'il existe 64 lignes d'adresse (processeurs x86-64), vous pouvez adresser 2 ⁶⁴ octets (16 exaoctets) de mémoire, mais la plupart des architectures qui utilisent des pointeurs 64 bits utilisent en fait des lignes d'adresse 48 bits (AMD64) et lignes d'adresse 42 bits (Intel), qui permettent théoriquement aux ordinateurs d'être équipés de 256 téraoctets de mémoire physique (Linux permet, sur l'architecture x86-64, lors de l'utilisation des pages d'adresse de niveau 4, d'allouer jusqu'à 128 To d'espace d'adressage aux processus, Windows vous permet d'allouer jusqu'à 192 To).
Comme la taille de la RAM physique est limitée, chaque processus s'exécute dans son propre "bac à sable" - dans ce que l'on appelle "l'espace d'adressage virtuel", appelé mémoire virtuelle.

Les adresses d'octet dans l'espace d'adressage virtuel ne correspondent pas aux adresses que le processeur utilise pour accéder à la mémoire physique. En conséquence, nous avons besoin d'un système qui nous permette de convertir des adresses virtuelles en adresses physiques. Jetez un œil à ce à quoi ressemblent les adresses de mémoire virtuelle.


Représentation de l'espace d'adressage virtuel

Par conséquent, lorsque le processeur exécute une instruction qui fait référence à une adresse mémoire, la première étape consiste à traduire l'adresse logique en une adresse linéaire. Cette conversion est effectuée par l'unité de gestion de la mémoire.


Représentation simplifiée de la relation entre mémoire virtuelle et mémoire physique

Étant donné que les adresses logiques sont trop grandes pour être pratiques pour les utiliser séparément (cela dépend de divers facteurs), la mémoire est organisée en structures appelées pages. Dans ce cas, l'espace d'adressage virtuel est divisé en petites zones, des pages qui, dans la plupart des systèmes d'exploitation, ont une taille de 4 Ko, bien que cette taille puisse généralement être modifiée. Il s'agit de la plus petite unité de gestion de la mémoire dans la mémoire virtuelle. La mémoire virtuelle ne stocke rien, elle établit simplement la correspondance entre l'espace d'adressage du programme et la mémoire physique.

Les processus ne voient que les adresses de mémoire virtuelle. Que se passe-t-il si un programme a besoin de plus de mémoire dynamique (également appelée mémoire de tas ou «tas»)? Voici un exemple de code assembleur simple dans lequel une mémoire supplémentaire allouée dynamiquement est demandée au système:

_start:        mov $12, %rax #    brk        mov $0, %rdi # 0 -  ,            syscall b0:        mov %rax, %rsi #  rsi    ,           mov %rax, %rdi #     ...        add $4, %rdi # ..  4 ,           mov $12, %rax #    brk        syscall 

Voici comment il peut être représenté sous forme de diagramme.


Augmentez la mémoire allouée dynamiquement

Le programme demande de la mémoire supplémentaire à l'aide de l'appel système brk (sbrk / mmap, etc.). Le noyau met à jour les informations sur la mémoire virtuelle, mais de nouvelles pages n'ont pas encore été présentées dans la mémoire physique, et ici il y a une différence entre la mémoire virtuelle et la mémoire physique.

Allocateur de mémoire

Après avoir, en termes généraux, discuté de l'utilisation de l'espace d'adressage virtuel, parlé de la façon de demander de la mémoire dynamique supplémentaire (mémoire sur le tas), il nous sera plus facile de parler des moyens d'allouer de la mémoire.

Si le tas a suffisamment de mémoire pour satisfaire nos requêtes de code, alors l'allocateur de mémoire peut exécuter ces requêtes sans accéder au noyau. Sinon, il doit augmenter la taille du tas en utilisant un appel système (en utilisant brk, par exemple), tout en demandant un gros bloc de mémoire. Dans le cas de malloc, «grand» signifie la taille décrite par le paramètre MMAP_THRESHOLD , qui, par défaut, est de 128 Ko.

Cependant, un allocateur de mémoire a plus de responsabilités que d'allouer simplement de la mémoire. L'une de ses responsabilités les plus importantes est de réduire la fragmentation de la mémoire interne et externe et d'allouer les blocs de mémoire le plus rapidement possible. Supposons que notre programme exécute séquentiellement des demandes d'allocation de blocs de mémoire continus à l'aide d'une fonction de la forme malloc(size) , après quoi cette mémoire est libérée à l'aide d'une fonction de la forme free(pointer) .


Démonstration de fragmentation externe

Dans le diagramme précédent, à l'étape p4, nous n'avons pas suffisamment de blocs de mémoire situés séquentiellement pour répondre à la demande d'allocation de six de ces blocs, bien que la quantité totale de mémoire libre le permette. Cette situation entraîne une fragmentation de la mémoire.

Comment réduire la fragmentation de la mémoire? La réponse à cette question dépend de l'algorithme d'allocation de mémoire spécifique, sur lequel la bibliothèque de base est utilisée pour travailler avec la mémoire.

Nous allons maintenant examiner l'outil d'allocation de mémoire TCMalloc, sur lequel les mécanismes d'allocation de mémoire Go sont basés.

TCMalloc

TCMalloc est basé sur l'idée de diviser la mémoire en plusieurs niveaux pour réduire la fragmentation de la mémoire. Dans TCMalloc, la gestion de la mémoire est divisée en deux parties: travailler avec la mémoire des threads et travailler avec le tas.

▍ Mémoire de thread

Chaque page de mémoire est divisée en une séquence de fragments de certaines tailles, sélectionnés en fonction des classes de taille. Cela réduit la fragmentation. De ce fait, chaque thread dispose d'un cache pour les petits objets, ce qui permet une allocation très efficace de la mémoire pour les objets inférieurs ou égaux à 32 Ko.


Cache de flux

▍Bunch

Un tas géré TCMalloc est une collection de pages dans laquelle un ensemble de pages consécutives peut être représenté comme une plage de pages (span). Lorsque vous devez allouer de la mémoire à un objet dont la taille est supérieure à 32 Ko, le segment de mémoire est utilisé pour allouer de la mémoire.


Tassez et travaillez avec des pages

Lorsqu'il n'y a pas assez d'espace pour placer de petits objets en mémoire, ils se tournent vers le tas de mémoire. Si le tas n'a pas assez de mémoire libre, une mémoire supplémentaire est demandée au système d'exploitation.

Par conséquent, le modèle présenté de travail avec la mémoire prend en charge le pool de mémoire de l'espace utilisateur; son utilisation améliore considérablement l'efficacité de l'allocation et de la libération de mémoire.

Il convient de noter que l'outil d'allocation de mémoire Go était à l'origine basé sur TCMalloc, mais il en diffère légèrement.

Go allocateur de mémoire

Nous savons que le runtime Go prévoit d'exécuter des goroutines sur des processeurs logiques. De même, la version de TCMalloc utilisée par Go divise les pages mémoire en blocs dont les tailles correspondent à certaines classes de taille dont 67 existent.

Si vous n'êtes pas familier avec le planificateur Go , vous pouvez en lire plus ici .


Allez classes de taille

Étant donné que la taille de page minimale dans Go est de 8192 octets (8 Ko), si une telle page est divisée en blocs de 1 Ko, nous obtiendrons 8 de ces blocs.


Une taille de page de 8 Ko est divisée en blocs correspondant à une taille de classe de 1 Ko

Les séquences de pages similaires dans Go sont contrôlées à l'aide d'une structure appelée mspan.

▍Structure mspan

La structure mspan est une liste doublement liée, un objet qui contient l'adresse de départ de la page, des informations sur la taille de la page et le nombre de pages qu'elle contient.


Structure Mspan

▍ structure mcache

Comme TCMalloc, Go fournit à chaque processeur logique un cache de thread local, appelé mcache. Par conséquent, si goroutine a besoin de mémoire, il peut l'obtenir directement depuis mcache. Pour ce faire, vous n'avez pas besoin d'effectuer de verrouillage, car à tout moment, un seul goroutin est exécuté sur un processeur logique.

La structure mcache contient, sous forme de cache, des structures mspan de différentes classes de taille.


Interaction entre processeur logique, mcache et mspan dans Go

Étant donné que chaque processeur logique a son propre mcache, il n'est pas nécessaire de verrouiller lors de l'allocation de mémoire à partir de mcache.

Chaque classe de taille peut être représentée par l'un des objets suivants:

• Un objet numérisé est un objet qui contient un pointeur.
• Un objet noscan est un objet dans lequel il n'y a pas de pointeur.

L'une des forces de cette approche est que lorsque la récupération de place est effectuée, les objets noscan n'ont pas besoin d'être contournés, car ils ne contiennent pas d'objets pour lesquels de la mémoire est allouée.

Qu'est-ce qui entre dans mache? Les objets dont la taille ne dépasse pas 32 Ko vont directement à mcache en utilisant mspan de la classe de taille correspondante.

Que se passe-t-il si mcache n'a pas de cellule libre? Ensuite, ils obtiennent un nouveau mspan de la classe de taille souhaitée dans la liste des objets mspan appelés mcentral.

Structure Structure centrale

La structure mcentral collecte toutes les plages de pages d'une classe de taille particulière. Chaque objet mcentral contient deux listes d'objets mspan.

1. Liste des objets mspan dans lesquels il n'y a pas d'objets libres, ou ceux mspan qui sont dans mcache.
2. Liste des objets mspan contenant des objets libres.

Structure Mcentral

Chaque structure mcentral existe au sein de la structure mheap.

Structure Structure de tas

La structure mheap est représentée par un objet qui gère la gestion des segments dans Go. Un seul objet global de ce type possède un espace d'adressage virtuel.


Structure mheap

Comme vous pouvez le voir sur le diagramme ci-dessus, la structure mheap contient un tableau de structures mcentral. Ce tableau contient des structures mcentral pour toutes les classes de taille.

 central [numSpanClasses]struct { mcentral mcentral   pad     [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte } 

Étant donné que nous avons une structure mcentral pour chaque classe de taille, lorsque mcache demande la structure mspan à mcentral, un verrou est appliqué au niveau mcentral individuel, par conséquent, les demandes d'autres mcache demandant des structures mspan d'autres tailles peuvent être servies en même temps.

L'alignement (pad) garantit que les structures mcentral sont séparées les unes des autres par le nombre d'octets correspondant à la valeur CacheLineSize . En conséquence, chaque mcentral.lock a sa propre ligne de cache, ce qui évite les problèmes associés au partage de fausses mémoires.

Que se passe-t-il si la liste mcentral est vide? Ensuite, mcentral reçoit une séquence de pages de mheap pour allouer des fragments de mémoire de la classe de taille requise.

• free[_MaxMHeapList]mSpanList est un tableau de spanList. La structure mspan dans chaque spanList se compose de 1 à 127 pages (_MaxMHeapList - 1). Par exemple, free [3] est une liste chaînée de structures mspan contenant 3 pages. Le mot "libre" dans ce cas indique que nous parlons d'une liste vide dans laquelle la mémoire n'est pas allouée. Une liste peut être, par opposition à vide, une liste dans laquelle la mémoire est allouée (occupée).
• freelarge mSpanList est une liste de structures mspan libres. Le nombre de pages par élément (c'est-à-dire, mspan) est supérieur à 127. Pour prendre en charge cette liste, la structure de données mtreap est utilisée. La liste des structures mspan occupées est appelée busylarge.

Les objets supérieurs à 32 Ko sont considérés comme des objets volumineux, leur mémoire est allouée directement à partir de mheap. Les demandes d'allocation de mémoire pour de tels objets sont effectuées à l'aide d'un verrou, par conséquent, à un moment donné, une demande similaire peut être traitée à partir d'un seul processeur logique.

Processus d'allocation de mémoire aux objets

• Si la taille de l'objet dépasse 32 Ko, il est considéré comme grand, la mémoire pour lui est allouée directement à partir de mheap.
• Si la taille de l'objet est inférieure à 16 Ko, le mécanisme mcache appelé allocateur minuscule est utilisé.
• Si la taille de l'objet est comprise entre 16 et 32 ​​Ko, il s'avère que la classe de taille (sizeClass) à utiliser, puis un bloc approprié est alloué dans mcache.
• S'il n'y a pas de blocs disponibles dans la classe de taille correspondant à mcache, mcentral est appelé.
• Si mcentral n'a pas de blocs libres, alors ils appellent mheap et recherchent le mspan le plus approprié. Si la taille de mémoire requise par l'application s'avère supérieure à ce qu'il est possible d'allouer, la taille de mémoire demandée sera traitée afin qu'il soit possible de renvoyer autant de pages que le programme le souhaite, après avoir formé une nouvelle structure mspan.
• Si la mémoire virtuelle de l'application n'est toujours pas suffisante, le système d'exploitation est accessible pour un nouvel ensemble de pages (au moins 1 Mo de mémoire est requis).

En fait, au niveau du système d'exploitation, Go demande l'allocation de pièces de mémoire encore plus grandes appelées arènes. L'allocation simultanée de gros fragments de mémoire vous permet de trouver un compromis entre la quantité de mémoire allouée à l'application et l'accès coûteux au système d'exploitation en termes de performances.

La mémoire demandée sur le tas est allouée depuis l'arène. Considérez ce mécanisme.

Mémoire virtuelle go

Jetez un œil à l'utilisation de la mémoire avec un programme simple écrit en Go:

 func main() {   for {} } 

Informations sur le processus du programme

L'espace d'adressage virtuel d'un programme aussi simple est d'environ 100 Mo, tandis que l'index RSS n'est que de 696 Ko. Tout d'abord, essayons de trouver la raison de cet écart.


Carte et informations sur la carte

Vous pouvez voir ici les zones de mémoire, dont la taille est approximativement égale à 2 Mo, 64 Mo, 32 Mo. Quel genre de mémoire est-ce?

▍Arena

Il s'avère que la mémoire virtuelle dans Go se compose d'un ensemble d'arènes. La taille de mémoire initiale destinée au tas correspond à une arène, soit - 64 Mo (ceci est pertinent pour Go 1.11.5).


Taille actuelle de l'aréna dans divers systèmes

En conséquence, la mémoire nécessaire pour les besoins actuels du programme est allouée en petites portions. Ce processus commence par une arène de 64 Mo.

Ces indicateurs numériques dont nous parlons ici ne doivent pas être pris pour certaines valeurs absolues et inchangées. Ils peuvent changer. Plus tôt, par exemple, Go avait réservé un espace virtuel continu à l'avance, sur les systèmes 64 bits, la taille de l'arène était de 512 Go (il est intéressant de penser à ce qui se passe si la demande de mémoire réelle est si importante que la demande correspondante sera rejetée par mmap?).

En fait, nous appelons un tas d'arènes un tas. Dans Go, les arènes sont perçues comme des fragments de mémoire, divisés en blocs de 8192 octets (8 Ko).


Une arène de 64 Mo

Go a quelques autres saveurs de blocs - span et bitmap. La mémoire pour eux est allouée en dehors du tas, ils stockent les métadonnées de l'arène. Ils sont principalement utilisés dans la collecte des ordures.
Voici un aperçu général du fonctionnement des mécanismes d'allocation de mémoire dans Go.


Aperçu général des mécanismes d'allocation de mémoire dans Go

Résumé

En général, on peut noter que dans ce document, nous avons décrit les sous-systèmes pour travailler avec la mémoire Go en termes très généraux. L'idée principale du sous-système de mémoire dans Go est d'allouer de la mémoire en utilisant différentes structures et caches de différents niveaux. Cela prend en compte la taille des objets auxquels la mémoire est allouée.

La représentation d'un seul bloc d'adresses de mémoire continue reçues du système d'exploitation sous la forme d'une structure à plusieurs niveaux augmente l'efficacité du mécanisme d'allocation de mémoire du fait que cette approche évite le blocage. L'allocation des ressources, en tenant compte de la taille des objets qui doivent être stockés en mémoire, réduit la fragmentation et, après avoir libéré de la mémoire, vous permet d'accélérer le garbage collection.

Chers lecteurs! Avez-vous rencontré des problèmes dus à un dysfonctionnement de la mémoire dans les programmes écrits en Go?