Ir mecanismos de alocação

Quando tentei entender como as ferramentas de alocação de memória no Go funcionam, o que eu queria lidar parecia uma caixa preta misteriosa. Como em qualquer outra tecnologia, a coisa mais importante aqui está oculta por trás de muitas camadas de abstrações, pelas quais você precisa passar para entender alguma coisa.



O autor do material, cuja tradução estamos publicando, decidiu chegar ao fundo dos meios de alocação de memória no Go e falar sobre isso.

Memória física e virtual

Todos os meios para alocar memória precisam trabalhar com o espaço de endereço da memória virtual, que é controlada pelo sistema operacional. Vamos ver como a memória funciona, começando no nível mais baixo - com células de memória.
Veja como imaginar uma célula RAM.


Layout da célula de memória

Se, muito simplificado, imaginar uma célula de memória e o que a rodeia, obtemos o seguinte:

1. A linha de endereço (o transistor atua como um comutador) é o que dá acesso ao capacitor (linha de dados).
2. Quando um sinal aparece na linha de endereço (linha vermelha), a linha de dados permite gravar dados na célula de memória, ou seja, carregar o capacitor, o que possibilita armazenar um valor lógico correspondente a 1 nele.
3. Quando não há sinal na linha de endereço (linha verde), o capacitor é isolado e sua carga não muda. Para gravar na célula 0, você deve selecionar seu endereço e enviar um 0 lógico pela linha de dados, ou seja, conectar a linha de dados com um sinal de menos, descarregando assim o capacitor.
4. Quando o processador precisa ler o valor da memória, o sinal é enviado ao longo da linha de endereço (a chave fecha). Se o capacitor estiver carregado, o sinal passa pela linha de dados (1 é lido), caso contrário, o sinal não passa pela linha de dados (0 é lido).

O esquema de interação da memória física e do processador

O barramento de dados é responsável pelo transporte de dados entre o processador e a memória física.

Agora vamos falar sobre a linha de endereço e os bytes endereçáveis.


Linhas de endereço de barramento entre o processador e a memória física

1. Cada byte na RAM recebe um identificador numérico (endereço) exclusivo. Note-se que o número de bytes físicos presentes na memória não é igual ao número de linhas de endereço.
2. Cada linha de endereço pode especificar um valor de 1 bit, indicando um bit no endereço de um determinado byte.
3. Nosso circuito possui 32 linhas de endereço. Como resultado, cada byte endereçável usa um número de 32 bits como endereço. [00000000000000000000000000000000] - o menor endereço de memória. [1111111111111111111111111111111111] - o endereço de memória mais alto.
4. Como cada byte possui um endereço de 32 bits, nosso espaço de endereço consiste em 2 ³² bytes endereçáveis ​​(4 GB).

Como resultado, verifica-se que o número de bytes endereçáveis ​​depende do número total de linhas de endereço. Por exemplo, se houver 64 linhas de endereço (processadores x86-64), é possível endereçar 2 ⁶⁴ bytes (16 exabytes) de memória, mas a maioria das arquiteturas que usam ponteiros de 64 bits na verdade usa linhas de endereço de 48 bits (AMD64) e linhas de endereço de 42 bits (Intel), que teoricamente permitem que os computadores sejam equipados com 256 terabytes de memória física (o Linux permite, na arquitetura x86-64, ao usar páginas de endereço de nível 4, alocar até 128 TB de espaço de endereço para processos, o Windows permite alocar até 192 TB).
Como o tamanho da RAM física é limitado, cada processo é executado em sua própria "caixa de areia" - no chamado "espaço de endereço virtual", chamado memória virtual.

Os endereços de bytes no espaço de endereço virtual não correspondem aos endereços que o processador usa para acessar a memória física. Como resultado, precisamos de um sistema que nos permita converter endereços virtuais em físicos. Veja como são os endereços de memória virtual.


Representação de espaço de endereço virtual

Como resultado, quando o processador executa uma instrução que se refere a um endereço de memória, a primeira etapa é converter o endereço lógico em um endereço linear. Essa conversão é realizada pela unidade de gerenciamento de memória.


Representação simplificada do relacionamento entre memória virtual e física

Como os endereços lógicos são grandes demais para serem convenientes para trabalhar com eles separadamente (isso depende de vários fatores), a memória é organizada em estruturas chamadas páginas. Nesse caso, o espaço de endereço virtual é dividido em pequenas áreas, páginas, que na maioria dos sistemas operacionais têm 4 KB de tamanho, embora geralmente esse tamanho possa ser alterado. Essa é a menor unidade de gerenciamento de memória da memória virtual. A memória virtual não armazena nada, simplesmente define a correspondência entre o espaço de endereço do programa e a memória física.

Os processos veem apenas endereços de memória virtual. O que acontece se um programa precisar de mais memória dinâmica (também chamada de memória heap ou "heap")? Aqui está um exemplo de código assembler simples no qual a memória alocada dinamicamente adicional é solicitada ao sistema:

_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 

Aqui está como ele pode ser representado na forma de um diagrama.


Aumentar memória alocada dinamicamente

O programa solicita memória adicional usando a chamada do sistema brk (sbrk / mmap e assim por diante). O kernel atualiza as informações sobre memória virtual, mas novas páginas ainda não foram apresentadas na memória física, e aqui há uma diferença entre a memória virtual e a física.

Alocador de memória

Depois que, em termos gerais, discutimos o trabalho com o espaço de endereço virtual, falamos sobre como solicitar memória dinâmica adicional (memória na pilha), será mais fácil falar sobre meios para alocar memória.

Se o heap tiver memória suficiente para satisfazer nossas solicitações de código, o alocador de memória poderá executar essas solicitações sem acessar o kernel. Caso contrário, ele precisará aumentar o tamanho do heap usando uma chamada do sistema (usando brk, por exemplo), enquanto solicita um grande bloco de memória. No caso do malloc, “grande” significa o tamanho descrito pelo parâmetro MMAP_THRESHOLD , que, por padrão, é de 128 Kb.

No entanto, um alocador de memória tem mais responsabilidades do que simplesmente alocar memória. Uma de suas responsabilidades mais importantes é reduzir a fragmentação de memória interna e externa e alocar blocos de memória o mais rápido possível. Suponha que nosso programa execute sequencialmente solicitações para alocar blocos contínuos de memória usando uma função do formulário malloc(size) , após o qual essa memória é liberada usando uma função do formulário free(pointer) .


Demonstração de fragmentação externa

No diagrama anterior, na etapa p4, não temos blocos de memória localizados em sequência suficientes para atender à solicitação de alocação de seis desses blocos, embora a quantidade total de memória livre permita isso. Essa situação leva à fragmentação da memória.

Como reduzir a fragmentação da memória? A resposta a esta pergunta depende do algoritmo de alocação de memória específico, no qual a biblioteca base é usada para trabalhar com memória.

Agora, veremos a ferramenta de alocação de memória TCMalloc, na qual os mecanismos de alocação de memória Go são baseados.

TCMalloc

O TCMalloc é baseado na idéia de dividir a memória em vários níveis para reduzir a fragmentação da memória. No TCMalloc, o gerenciamento de memória é dividido em duas partes: trabalhando com a memória de threads e trabalhando com heap.

▍ Memória da thread

Cada página da memória é dividida em uma sequência de fragmentos de determinados tamanhos, selecionados de acordo com as classes de tamanho. Isso reduz a fragmentação. Como resultado, cada encadeamento tem à sua disposição um cache para objetos pequenos, o que permite uma alocação muito eficiente de memória para objetos menores ou iguais a 32 KB.


Cache de fluxo

▍

Um heap gerenciado pelo TCMalloc é uma coleção de páginas na qual um conjunto de páginas consecutivas pode ser representado como um intervalo de páginas (extensão). Quando você precisa alocar memória para um objeto maior que 32 KB, o heap é usado para alocar memória.


Empilhe e trabalhe com páginas

Quando não há espaço suficiente para colocar pequenos objetos na memória, eles recorrem à pilha de memória. Se o heap não tiver memória livre suficiente, será solicitada memória adicional ao sistema operacional.

Como resultado, o modelo apresentado de trabalho com memória suporta o pool de memória do espaço do usuário; seu uso melhora significativamente a eficiência da alocação e liberação de memória.

Deve-se observar que a ferramenta de alocação de memória Go foi originalmente baseada no TCMalloc, mas difere um pouco dela.

Alocador de memória Go

Sabemos que o tempo de execução do Go planeja executar goroutines em processadores lógicos. Da mesma forma, a versão do TCMalloc usada pelo Go divide as páginas de memória em blocos cujos tamanhos correspondem a determinadas classes de tamanho das quais 67 existem.

Se você não está familiarizado com o planejador Go , pode ler sobre isso aqui .


Ir para classes de tamanho

Como o tamanho mínimo da página no Go é 8192 bytes (8 Kb), se essa página for dividida em blocos de 1 KB, obteremos 8 desses blocos.


Um tamanho de página de 8 KB é dividido em blocos correspondentes a um tamanho de classe de 1 KB

Sequências de páginas semelhantes no Go são controladas usando uma estrutura chamada mspan.

PanEstrutura mspan

A estrutura mspan é uma lista duplamente vinculada, um objeto que contém o endereço inicial da página, informações sobre o tamanho da página e o número de páginas incluídas nela.


Estrutura Mspan

▍ estrutura do mcache

Como o TCMalloc, o Go fornece a cada processador lógico um cache de encadeamento local, conhecido como mcache. Como resultado, se a goroutine precisar de memória, poderá obtê-la diretamente do mcache. Para fazer isso, você não precisa executar bloqueios, pois a qualquer momento, apenas uma goroutin é executada em um processador lógico.

A estrutura mcache contém, na forma de um cache, estruturas mspan de várias classes de tamanho.


Interação entre processador lógico, mcache e mspan no Go

Como cada processador lógico possui seu próprio mcache, não há necessidade de bloqueios ao alocar memória do mcache.

Cada classe de tamanho pode ser representada por um dos seguintes objetos:

• Um objeto de digitalização é um objeto que contém um ponteiro.
• Um objeto noscan é um objeto no qual não há ponteiro.

Um dos pontos fortes dessa abordagem é que, quando a coleta de lixo é realizada, os objetos noscan não precisam ser contornados, pois não contêm objetos para os quais a memória está alocada.

O que entra no mcache? Objetos cujo tamanho não exceda 32 KB vão diretamente para o mcache usando mspan da classe de tamanho correspondente.

O que acontece se o mcache não tiver uma célula livre? Em seguida, eles obtêm um novo mspan da classe de tamanho desejada da lista de objetos mspan chamados mcentral.

Estrutura central

A estrutura mcentral coleta todos os intervalos de páginas de uma classe de tamanho específica. Cada objeto mcentral contém duas listas de objetos mspan.

1. Lista de objetos mspan nos quais não há objetos livres ou aqueles que estão no mcache.
2. Lista de objetos mspan que possuem objetos livres.

Estrutura central

Cada estrutura mcentral existe dentro da estrutura mheap.

Estrutura da pilha

A estrutura mheap é representada por um objeto que lida com o gerenciamento de heap no Go. Existe apenas um objeto global que possui um espaço de endereço virtual.


Estrutura Mheap

Como você pode ver no diagrama acima, a estrutura mheap contém uma matriz de estruturas mcentrais. Essa matriz contém estruturas centrais para todas as classes de tamanho.

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

Como temos uma estrutura mcentral para cada classe de tamanho, quando o mcache solicita a estrutura mspan do mcentral, um bloqueio é aplicado no nível mcentral individual; como resultado, solicitações de outros mcache que solicitam estruturas mspan de outros tamanhos podem ser atendidas ao mesmo tempo.

O alinhamento (pad) garante que as estruturas mcentrais sejam separadas uma da outra pelo número de bytes correspondentes ao valor CacheLineSize . Como resultado, cada mcentral.lock possui sua própria linha de cache, o que evita os problemas associados ao compartilhamento de memória falsa.

O que acontece se a lista central estiver vazia? O mcentral recebe uma sequência de páginas do mheap para alocar fragmentos de memória da classe de tamanho necessária.

• free[_MaxMHeapList]mSpanList é uma matriz de spanList. A estrutura mspan em cada spanList consiste em 1 a 127 páginas (_MaxMHeapList - 1). Por exemplo, free [3] é uma lista vinculada de estruturas mspan contendo 3 páginas. A palavra "livre", neste caso, indica que estamos falando de uma lista vazia na qual a memória não está alocada. Uma lista pode ser, ao contrário de vazia, uma lista na qual a memória está alocada (ocupada).
• freelarge mSpanList é uma lista de estruturas gratuitas do mspan. O número de páginas por elemento (ou seja, mspan) é maior que 127. Para suportar esta lista, a estrutura de dados mtreap é usada. A lista de estruturas de mspan ocupadas é chamada de busylarge.

Objetos maiores que 32 Kb são considerados objetos grandes, a memória para eles é alocada diretamente do mheap. As solicitações para alocar memória para esses objetos são executadas usando um bloqueio, como resultado, em um determinado momento, uma solicitação semelhante pode ser processada a partir de apenas um processador lógico.

O processo de alocar memória para objetos

• Se o tamanho do objeto exceder 32 Kb, ele será considerado grande, a memória para ele será alocada diretamente do mheap.
• Se o tamanho do objeto for menor que 16 Kb, o mecanismo mcache chamado tiny alocador será usado.
• Se o tamanho do objeto estiver no intervalo de 16 a 32 Kb, descobrirá qual classe de tamanho (sizeClass) usar, um bloco adequado será alocado no mcache.
• Se não houver blocos disponíveis no sizeClass correspondentes ao mcache, o mcentral será chamado.
• Se o mcentral não tiver blocos livres, eles chamarão mheap e procurarão o mspan mais adequado. Se o tamanho da memória exigido pelo aplicativo for maior do que é possível alocar, o tamanho da memória solicitada será processado para que seja possível retornar quantas páginas forem necessárias pelo programa, tendo formado uma nova estrutura mspan.
• Se a memória virtual do aplicativo ainda não for suficiente, o sistema operacional será acessado para um novo conjunto de páginas (pelo menos 1 MB de memória é solicitado).

De fato, no nível do sistema operacional, o Go solicita a alocação de pedaços de memória ainda maiores, chamados arenas. A alocação simultânea de grandes fragmentos de memória permite encontrar um compromisso entre a quantidade de memória alocada ao aplicativo e o caro acesso ao sistema operacional em termos de desempenho.

A memória solicitada no heap é alocada na arena. Considere esse mecanismo.

Memória virtual

Dê uma olhada no uso da memória com um programa simples escrito em Go:

 func main() {   for {} } 

Informações do processo do programa

O espaço de endereço virtual de um programa tão simples é de aproximadamente 100 MB, enquanto o índice RSS é de apenas 696 Kb. Primeiro, vamos tentar descobrir o motivo dessa discrepância.


Informações de mapa e smap

Aqui você pode ver as áreas de memória, cujo tamanho é aproximadamente igual a 2 MB, 64 MB, 32 MB. Que tipo de memória é essa?

▍Arena

Acontece que a memória virtual no Go consiste em um conjunto de arenas. O tamanho da memória inicial destinado ao heap corresponde a uma arena, ou seja, 64 MB (isso é relevante para o Go 1.11.5).


Tamanho atual da arena em vários sistemas

Como resultado, a memória necessária para as necessidades atuais do programa é alocada em pequenas porções. Esse processo começa com uma arena de 64 MB.

Esses indicadores numéricos sobre os quais estamos falando aqui não devem ser tomados por alguns valores absolutos e inalterados. Eles podem mudar. Antes, por exemplo, a Go reservava um espaço virtual contínuo e antecipadamente, em sistemas de 64 bits, o tamanho da arena era de 512 GB (é interessante pensar no que acontece se a demanda de memória real for tão grande que a solicitação correspondente será rejeitada pelo mmap?).

De fato, chamamos um monte de arenas de monte. No Go, as arenas são percebidas como fragmentos de memória, divididos em blocos de 8192 bytes (8 Kb) de tamanho.


Uma arena de 64 MB

Go tem mais alguns tipos de blocos - span e bitmap. A memória para eles é alocada fora da pilha, eles armazenam metadados da arena. Eles são usados ​​principalmente na coleta de lixo.
Aqui está um resumo geral de como os mecanismos de alocação de memória funcionam no Go.


Descrição geral dos mecanismos de alocação de memória no Go

Sumário

Em geral, pode-se notar que neste material descrevemos os subsistemas para trabalhar com a memória Go em termos muito gerais. A idéia principal do subsistema de memória no Go é alocar memória usando várias estruturas e caches de diferentes níveis. Isso leva em consideração o tamanho dos objetos para os quais a memória está alocada.

A representação de um único bloco de endereços de memória contínua recebidos do sistema operacional na forma de uma estrutura multinível aumenta a eficiência do mecanismo de alocação de memória devido ao fato de que essa abordagem evita o bloqueio. A alocação de recursos, levando em consideração o tamanho dos objetos que precisam ser armazenados na memória, reduz a fragmentação e, após liberar memória, permite acelerar a coleta de lixo.

Caros leitores! Você encontrou problemas causados ​​pelo mau funcionamento da memória em programas escritos no Go?