Alocação de memória do sistema usando o subsistema malloc

A memória é alocada para aplicativos usando o subsistema malloc .

O subsistema malloc é uma API de gerenciamento de memória que consiste nas seguintes subroutines:

• malloc
• calloc
• realloc
• grátis
• mallopt
• mallinfo
• alloca
• valloc
• posix_memalign

O subsistema malloc gerencia um objeto de memória lógica chamado de heap. O heap é uma região de memória que reside no espaço de endereço do aplicativo entre o último byte de dados alocados pelo compilador e o fim da região de dados. O heap é o objeto de memória a partir do qual a memória é alocada e para a qual a memória é devolvida pela API do subsistema malloc .

As subroutines mallopt e mallinfo são suportadas para compatibilidade do System V. A subroutine mallinfo pode ser usada durante o desenvolvimento do programa para obter informações sobre o heap gerenciado pela subroutine malloc . A subroutine mallopt pode ser usada para despedir a memória livre de tamanho da página, e para ativar e desativar o alocador padrão. Semelhante à subroutine malloc , a subroutine valloc é fornecida para compatibilidade com a Biblioteca de Compatibilidade Berkeley.

Para informações adicionais, veja as seções a seguir:

Trabalhando com o heap do processo

_edata é um símbolo cujo endereço é o primeiro byte a seguir o último byte de dados do programa inicializado. O símbolo _edata refere-se ao início do heap do processo, que é ampliado pelo subsistema malloc quando o primeiro bloco de dados é alocado. O subsistema malloc amplia o heap do processo, aumentando o valor do brk do processo, o que denota o término do heap do processo. Isso é feito chamando o subroutine sbrk . O subsistema malloc expande o heap do processo como as necessidades do aplicativo ditam.

O heap do processo é dividido em blocos de memória alocados e libertados . O conjunto livre consiste na memória disponível para alocação subsequente. Uma alocação é concluída através da primeira remoção de um bloco de memória do conjunto livre e, em seguida, retornando para a função de chamada um ponteiro para este bloco. Uma realocação é concluída alocando um bloco de memória do novo tamanho, movendo os dados no bloco original para o novo bloco, e liberando o bloco original. Os blocos de memória alocados consistem nas peças do heap do processo que estão sendo usadas pelo aplicativo. Como os blocos de memória não são removidos fisicamente do heap (eles mudam de estado de livre para alocados), o tamanho do heap do processo não diminui quando a memória é liberada pelo aplicativo.

Espaço de endereço de processo em 32-bit aplicativos

Um programa de aplicação de 32-bit em execução no sistema possui um espaço de endereço que é dividido nos seguintes segmentos:

Espaço de endereço de processo em 64-bit aplicativos

Um programa de aplicação de 64-bit em execução no sistema possui um espaço de endereço que é dividido nos seguintes segmentos:

Compreender a política de alocação do sistema

A política de alocação refere-se ao conjunto de estruturas de dados e algoritmos empregados para representar o heap e para implementar alocação, desalocação e realocação. O subsistema malloc suporta várias políticas de alocação diferentes, incluindo a política de alocação padrão, a política de alocação do Watson, a política de alocação do malloc 3.1 e a política de alocação definida pelo usuário A API para acessar o subsistema malloc é idêntica para todas as políticas de alocação; somente a implementação subjacente é diferente.

A política de alocação padrão é geralmente mais eficiente e é a escolha preferencial para a maioria dos aplicativos. As outras políticas de alocação possuem algumas características comportamentais exclusivas que podem ser benéticas em circunstâncias específicas, conforme descrito em Comparando as Políticas de Alocação diferente.

Algumas opções para as várias políticas de alocação são compatíveis entre si e podem ser utilizadas em tandem. Quando você estiver usando opções em tandem, use uma vírgula (,) para separar opções especificadas pelas variáveis de ambiente MALLOCOPTIONS e MALLOCDEBUG .

MALLOCALIGN=16;  export MALLOCALIGN

Além disso, internamente a um programa, o programa pode usar a rotina mallopt (M_MALIGN, 16) para alterar o padrão malloc () para fornecer 16-byte alocações alinhadas. A rotina mallopt (M_MALIGN) permite que um programa controle o alinhamento malloc padrão dinamicamente em tempo de execução.

Entendendo a política de alocação padrão

A política de alocação padrão mantém o espaço livre no heap como nós em uma árvore de busca binária cartesiana na qual os nós são ordenados de esquerda para direita por endereço (aumentando o endereço para a direita) e topto-de-baixo por comprimento (tal que nenhuma criança é maior do que sua controladora). Essa estrutura de dados não impõe limitação sobre o número de tamanhos de blocos suportados pela árvore, permitindo uma ampla gama de tamanhos de blocos em potencial. As técnicas de reorganização de árvores otimizam os tempos de acesso para localização do nó, inserção e exclusão e também protegem contra a fragmentação.

A política de alocação padrão fornece suporte para as seguintes capacidades opcionais:

Alocação

Uma pequena quantidade de overhead é necessária para atender um pedido de alocação. Isso se deve à necessidade de um prefixo de metadados e à necessidade de alinhamento adequado de cada bloco de memória. O tamanho do prefixo de metadados para todas as alocações é de 8 e 16 bytes para programas de 32-bit e 64-bit, respectivamente. Cada bloco deve estar alinhado em um limite de 16 ou 32 byte, assim, a quantidade total de memória necessária para uma alocação de tamanho n é:

size = roundup(n + prefix_size, alignment requirement)

Por exemplo, uma alocação de tamanho 37 em um processo de 32-bit exigiria roundup(37 + 8, 16), que é igual a 48 bytes.

O nó da árvore com o endereço mais baixo que é maior ou igual ao tamanho necessário é retirado da árvore. Se o bloco encontrado for maior do que o tamanho necessário, o bloco é dividido em dois blocos: um do tamanho necessário, e o segundo um restante. O segundo bloco, chamado de runt, é voltado para a árvore livre para alocação futura. O primeiro bloco é voltado para o ouvinte.

Se um bloco de tamanho suficiente não for encontrado na árvore livre, o heap é expandido, um bloco do tamanho da extensão adquirida é adicionado à árvore livre, e a alocação continua conforme descrito anteriormente.

Dealocação

Blocos de memória desalocados com a subroutine free são devolvidos à árvore, na raiz. Cada nó ao longo do caminho até o ponto de inserção para o novo nó é examinado para ver se ele adentra o nó que está sendo inserido. Se ele fizer, os dois nós são mesclados e o nó recém-mesclado é realocado na árvore. Se nenhum bloco adjunta for encontrado, o nó é simplesmente inserido no local apropriado na árvore. Mesclar blocos adjacentes pode reduzir significativamente a fragmentação de heap.

Realocação

Se o tamanho do bloco realocado será maior que o bloco original, o bloco original é voltado para a árvore livre com a subroutina livre para que qualquer coalescência possível possa ocorrer. Um novo bloco do tamanho solicitado é então alocado, os dados são movidos do bloco original para o novo bloco e o novo bloco é voltado para o chamador.

Se o tamanho do bloco realocado for menor que o bloco original, o bloco será dividido e o menor será voltado para a árvore livre.

Limitações

Entendendo a política de alocação do Watson

A política de alocação do Watson mantém o espaço livre no heap como nós em duas árvores rubro-negras separadas: uma classificada por endereço, a outra por tamanho. As árvores rubro-negras fornecem operações de árvore mais simples e eficientes do que as árvores cartesianas do alocador padrão, assim, a política de alocação do Watson é muitas vezes mais rápida que a inadimplência.

Alocação

A política de alocação do Watson tem os mesmos requisitos de sobrecabeça que a política de alocação padrão.

A árvore de tamanho é procurada para o menor bloco possível que é maior ou igual ao tamanho necessário. Este bloco é então removido da árvore de tamanho. Se o bloco encontrado for maior do que o tamanho necessário, o bloco é dividido em dois blocos: um bloco do tamanho restante, e o segundo do tamanho necessário. O primeiro bloco, chamado de runt, é voltado para a árvore de tamanho para alocação futura. O segundo bloco é voltado para o ouvinte. Se o bloco encontrado na árvore de tamanho era exatamente o tamanho necessário, o bloco é removido tanto do tamanho quanto da árvore de endereço e, em seguida, devolvido ao ouvinte.

Se um bloco de tamanho suficiente não for encontrado na árvore livre, o heap do processo é expandido, um bloco do tamanho dessa expansão é adicionado ao tamanho e árvores de endereço, e a alocação continua conforme descrito anteriormente.

Dealocação

Blocos de memória desalocados com a subroutine free são retornados para a árvore de endereço na raiz. Cada nó ao longo do caminho até o ponto de inserção para o novo nó é examinado para ver se ele adentra o nó que está sendo inserido. Se ele fizer, os dois nós são mesclados e o nó recém-mesclado é realocado na árvore de tamanho. Se nenhum bloco adjunta for encontrado, o nó é simplesmente inserido no local apropriado nos dois endereço e árvore de tamanho.

Após a inserção, ambas as árvores rubro-negras devem ser verificadas para balanceamento correto.

Realocação

Se o tamanho do bloco realocado será maior do que o bloco original, o bloco original é voltado para as árvores livres com a subroutina livre para que qualquer coalescência possível possa ocorrer. Um novo bloco do tamanho solicitado é então alocado, os dados são movidos do bloco original para o novo bloco e o novo bloco é voltado para o chamador.

Se o tamanho do bloco realocado for menor que o bloco original, o bloco será dividido e o restante será retornado para a árvore livre.

Limitações

Entendendo a política de alocação malloc 3.1

A política de alocação malloc 3.1 pode ser selecionada configurando MALLOCTYPE=3.1 antes da inicialização do processo.. Depois disso, todos os programas de 32 bits executados pelo shell usarão a política de alocação malloc 3.1 (programas de 64 bits continuarão a usar a política de alocação padrão).

size = 2 i + 4

Alocação

Um bloco é alocado a partir do conjunto livre por primeiro converter os bytes solicitados em um índice na matriz do balde, usando a seguinte equação:

needed = requested + 8

If needed <= 16,
then
bucket = 0

If needed > 16,
then
bucket = (log(needed)/log(2) rounded down to the nearest integer) - 3

O tamanho de cada bloco na lista ancorada pelo balde éblock size = 2 ^{bucket + 4}. Se a lista no balde for nula, a memória é alocada usando a subroutine sbrk para adicionar blocos à lista. Se o tamanho do bloco for menor que uma página, então uma página é alocada usando a subroutine sbrk , e o número de blocos chegados dividindo o tamanho do bloco no tamanho da página são adicionados à lista. Se o tamanho do bloco for igual ou maior que uma página, a memória necessária é alocada usando a subroutine sbrk , e um único bloco é adicionado à lista livre para o balde. Se a lista livre não estiver vazia, o bloco na cabeça da lista é voltado para o ouvinte. O próximo bloco da lista então passa a ser a nova cabeça.

Dealocação

Quando um bloco de memória é voltado para o conjunto livre, o índice do balde é calculado como com alocação. O bloco a ser liberado é então adicionado ao chefe da lista livre para o balde.

Realocação

Quando um bloco de memória é realocado, o tamanho necessário é comparado contra o tamanho existente do bloco. Por causa da ampla variância em tamanhos tratados por um único balde, o novo tamanho do bloco muitas vezes mapeia para o mesmo balde o tamanho do bloco original. Nestes casos, o comprimento do prefixo é atualizado para refletir o novo tamanho e o mesmo bloco é retornado. Se o tamanho necessário for maior do que o bloco existente, o bloco é liberado, um novo bloco é alocado a partir do novo balde, e os dados são movidos do bloco antigo para o novo bloco.

Limitações

Configurar MALLOCTYPE=3.1 ativará apenas a política malloc 3.1 para programas de 32 bits. Para que programas de 64 bits usem a política malloc 3.1 , a variável de ambiente MALLOCTYPE deve ser explicitamente configurada como MALLOCTYPE=3.1_64BIT Essa política de alocação é menos eficiente que a inadimplência e não é recomendada para uso na maioria dos casos.

A política de alocação malloc 3.1 suporta as seguintes opções:

• Disclamação de Malloc
• Entendendo a Opção no_overwrite

Entendendo a política de alocação de pool

Malloc pool é uma fronte frontal de alto desempenho para as funções libc malloc, calloc, free, posix_memalign e realloc para gerenciamento de objetos de armazenamento menores que 513 bytes. Os benefícios de desempenho derivam de comprimentos de trajeto dramaticamente mais curtos e melhor utilização de cache de dados. Para aplicações multiencadeadas, há o benefício adicional de que as âncoras da piscina local são usadas para evitar operações atômicas. Este fronte frontal pode ser usado em conjunto com qualquer um dos esquemas de gerenciamento de armazenamento atualmente fornecidos em libc (yorktowne watson).

export MALLOCOPTIONS=pool<:max_size>

Quando esta opção é especificada, uma coleção de conjuntos é criada durante a inicialização malloc onde cada pool é uma lista vinculada de objetos de tamanho fixo. O menor conjunto pode guardar objetos de pointer-size (como 8 bytes para 32-bit aplicativos ou 16 bytes para 64-bit aplicativos). Cada conjunto sucessivos pode acomodar objetos cujo tamanho é ponteiro-tamanho maior do que a piscina anterior. Isso significa que há 128 conjuntos para 32-bit aplicativos e 64 conjuntos para 64-bit aplicativos. A coleção de conjuntos é representada como uma matriz de ponteiros que "ancora" as listas vinculadas.

Malloc pool usa sua própria memória, o heap da piscina, que não é compartilhado com o padrão malloc. Quando especificado, a opção max_size é arredondada até o próximo valor de 2 MB superior e é usada para controlar o tamanho do heap da piscina. A opção max_size pode ser especificada como um número decimal ou um número hexadecimal precedido por 0x ou 0X (por exemplo, export MALLOCOPTIONS=pool:0x1700000 configurará max_size para 24 MB após arredondar para cima.

Para 32-bit aplicativos, o tamanho do heap da piscina começa em 2 MB. Se mais armazenamento for necessário e o armazenamento total do heap da piscina for menor que max_size, um adicional de 2 MB é adquirido. Cada área de 2 MBb estará em um limite de 2 MB, mas não precisa ser contígua a nenhuma das outras 2 MB áreas. Para aplicativos de 64-bit bits, um único heap de conjunto contíguo de max_size é alocado durante a inicialização malloc e nunca estendido. Se max_size não for especificado, ele será padronizado para 512 MB para 32-bit aplicativos e 32 MB para 64-bit aplicativos. Para os modos de 32 e 64-bit bits, max_size será configurado para 512 MB se um tamanho maior for especificado. Para o modo de 32 bits, o max_size é configurado como 512MBe para o modo de 64 bits, o max_size é configurado como 3.7 GB se um tamanho maior for especificado..

Utilização de Armazenamento

Todas as âncoras da piscina são inicialmente definidas como NULL ou vazias. Quando malloc serviços de piscina um pedido e o conjunto correspondente está vazio, uma rotina é chamada que aloca armazenamento do heap da piscina em contiguinhos de 1024-byte chunks em 1024-byte limites. Vários objetos do tamanho solicitado são "criados". O endereço do primeiro é voltado para satisfazer a solicitação, enquanto os demais objetos são vinculados e colocados na âncora da piscina. Para cada 1024-byte chunk, há uma entrada de 2-byte em uma tabela auxiliar que é usada por livre para determinar o tamanho de um objeto retornado.

Quando um objeto é liberado por conjunto malloc , ele é meramente "empurrado" sobre a âncora apropriada da piscina. Nenhuma tentativa é feita a blocos de coalesce para criar objetos de tamanho maior.

Devido a esse comportamento, o conjunto malloc pode usar mais armazenamento do que outras formas de malloc.

Alinhamento

O alinhamento padrão para as subroutines malloc (), calloc ()e realloc () deve ser especificado configurando-se a variável de ambiente MALLOCALIGN adequadamente. A subroutine do posix_memalign () continua trabalhando mesmo se a variável de ambiente MALLOCALIGN não for definida. Se MALLOCALIGN for maior que 512, o conjunto malloc não será usado.

eficiência de Cache

Os objetos de memória alocados com malloc pool não possuem prefixos ou sufixos. As linhas de cache de dados estão, portanto, mais densamente embaladas com dados utilizáveis do aplicativo Como todos os objetos de memória que são uma potência de 2 em tamanho estão alinhados em um limite igual a esse tamanho, cada objeto está contido dentro do número mínimo de linhas de cache. As subroutines malloc e free não digitam árvores ou listas vinculadas e, portanto, não "poluem" o cache.

Suporte multithreaded

Os conjuntos Malloc podem melhorar o desempenho significativamente em um cenário multiencadeado porque reduz a contenção de bloqueios e a necessidade de operações atômicas.

Suporte ao balanceamento de carga

Em alguns cenários multiencadeados, o conjunto livre de uma thread pode crescer muito devido à libertação repetitiva de memória alocada dinamicamente. No entanto, outras threads podem não ser capazes de usar esta memória.

O suporte de balanceamento de carga faz com que um fio libe metade da memória em cada piscina para um pool global após o pool atingir um valor limite para que outras threads possam utilizá-lo. Você pode ajustar os valores de limite no qual uma piscina de um fio será reajustada.

Para ligar o suporte de balanceamento de carga, as seguintes opções devem ser exportadas:

export MALLOCOPTIONS=pool:0x80000000,pool_balanced

export MALLOCFREEPOOL=min_size<-max_size>:threshold_value<,min_size<-max_size>:
threshold_value, ... >,default:threshold

export MALLOCFREEPOOL=0-16:256,32:512,default:128

Suporte de depuração

Não há versão de debug dessa fronte frontal de alto desempenho. Se a variável de ambiente MALLOCDEBUG for configurada, a opção de pool será ignorada. Espera-se que os aplicativos sejam depurados usando "normal" malloc antes de ativar a conjugação.

Entendendo a política de alocação definida pelo usuário

O subsistema malloc fornece um mecanismo através do qual os usuários podem desenvolver seus próprios algoritmos para gerenciamento do heap do sistema e alocação de memória.

Entendendo a opção no_overwrite

Uma opção adicional disponível para todas as políticas de alocação é no_overwrite. Para reduzir o overhead de código de glink dentro do subsistema malloc, o descritor de funções para as APIs do subsistema malloc são sobrescritas com o descritor de função para a implementação real subjacente. Como alguns programas, como depuradores de terceiros, podem não funcionar quando os ponteiros da função são modificados desta maneira, a opção no_overwrite pode ser usada para desabilitar essa otimização.

Para desativar essa otimização, configure MALLOCOPTIONS=no_overwrite antes da inicialização do processo.

Comparar as várias políticas de alocação

As várias políticas de alocação de malloc elaboradas acima fornecem flexibilidade aos desenvolvedores de aplicativos quando usadas separadamente ou combinadas de maneiras suportadas. É de responsabilidade do desenvolvedor reconhecer as necessidades exclusivas de um aplicativo e sintonia os diversos parâmetros de política de alocação de forma benéfica.

Comparando as políticas de alocação padrão e malloc 3.1

Como a política de alocação malloc 3.1 arredonda o tamanho de cada pedido de alocação para a próxima potência de 2, ela pode produzir considerável fragmentação de memória virtual e real e baixa localidade de referência. A política de alocação padrão é geralmente uma escolha melhor porque aloca exatamente a quantidade de espaço solicitada e é mais eficiente sobre a rereivindicação de blocos de memória usados anteriormente.

Infelizmente, alguns programas de aplicativos podem depender inadvertidamente de efeitos colaterais da política de alocação malloc 3.1 para desempenho aceitável ou mesmo para funcionamento correto. Por exemplo, um programa que ultrapassa o término de uma matriz pode funcionar corretamente ao usar o alocador malloc 3.1 apenas por causa do espaço adicional fornecido pelo processo de arredondamento. O mesmo programa provavelmente irá experimentar um comportamento errático ou até mesmo falhar quando usado com alocador padrão porque o alocador padrão aloca apenas o número de bytes solicitados.

Como outro exemplo, devido à recuperação de espaço ineficiente do algoritmo de alocação malloc 3.1 , o programa aplicativo quase sempre recebe espaço que foi configurado como zeros (quando um processo toca uma determinada página em seu segmento de trabalho pela primeira vez, essa página é configurada como zero). Os aplicativos podem depender deste efeito colaterais para a execução correta. Na verdade, zerar o espaço alocado não é uma função especificada da subroutine de malloc e resultaria em uma penalidade de desempenho desnecessária para programas que inicializam apenas como necessário e possivelmente não a zeros. Como o alocador padrão é mais agressivo sobre a reutilização do espaço, programas que são dependentes de recebimento de armazenamento zerado a partir de malloc provavelmente falharão quando o alocador padrão for usado.

Da mesma forma, se um programa continuamente realoca uma estrutura para um tamanho um pouco maior, o alocador malloc 3.1 pode não precisar mover a estrutura com muita frequência. Em muitos casos a sub-rotina realloc pode usar o espaço extra fornecido pelo arredondamento implícito no algoritmo de alocação malloc 3.1 . O alocador padrão geralmente terá que mover a estrutura para uma área um pouco maior por causa da probabilidade de que algo mais tenha sido chamado pela subroutine malloc logo acima dele. Isso pode apresentar a aparência de uma degradação no desempenho da sub-rotina realloc quando o alocador padrão é usado em vez do alocador malloc 3.1 Na realidade, é o surface de um custo que está implícito na estrutura do programa de aplicação.

Depurando o mau gerenciamento de aplicativos do heap do sistema

O subsistema malloc oferece uma coleção de ferramentas de depuração destinadas a ajudar o desenvolvedor de aplicativos a depurar e corrigir erros em um gerenciamento de heap do programa. Essas ferramentas de depuração são controladas através da variável de ambiente MALLOCDEBUG .

Sinopse da variável de ambiente malloc e opções

Entendendo a política de alocação do Watson2

O subsistema malloc Watson2 se adapta ao comportamento do aplicativo quando ele muda de uma thread única para várias threads e de várias threads para um único fio. Ele usa um mecanismo específico de encadeamento que usa um número variado de estruturas de heap, que dependem do comportamento do programa. Portanto, nenhuma opção de configuração é necessária. O subsistema malloc Watson2 tem O (logN) amortizado o custo por operação para várias cargas de trabalho porque um grande número de operações pode ser executado em um tempo constante sem sincronização...

Alocação

A alocação é tratada através de uma combinação de mecanismos. Esses mecanismos dependem de parâmetros, como o número de threads ativas, tamanho da solicitação e o histórico de desalocação do processo. O conjunto de mecanismos alcança a partir de um armazenamento em cache específico do fio e usa um número variável de saltos, que tem afinidade de encadeamento a uma coalescente dupla rubro-preta e coalescente à base de Page.

Dealocação

A desalocação depende dos mesmos parâmetros que o comportamento de alocação. Geralmente, um bloco de retorno é capturado no cache específico do encadeamento. Com base na afinidade de heap e utilização da capacidade, a memória pode ser devolvida a uma das múltiplas estruturas de heap. Por vezes, o conteúdo a partir da estrutura de múltiplos heap é consolidado a uma estrutura de heap comum para melhorar a coalescência e para reduzir a fragmentação de heap. Para melhorar a robustez contra os erros de aplicação, o alocador identifica desalocação de ponteiros inválidos ou blocos corrompidos, até certo grau e filtra essas operações.

Realocação

Grandes blocos de memória que são adequados são reutilizados. Se o bloco atual não puder satisfazer a solicitação, ele é substituído por uma desalocação e alocação regular.

Limitações

O subsistema de malloc Watson2 é adaptativo ao aplicativo e não requer mais opções, mas o subsistema malloc Watson2 suporta os seguintes recursos de depuração que são controlados pela variável MALLOCDEBUG : validate_ptrs, report_allocations, e trace. Os relatórios que estão relacionados a alocações podem ser redirecionados para um arquivo usando a opção output:<filename> . Veja ferramenta Debug malloc para obter informações detalhadas sobre a variável MALLOCDEBUG .