Alocação de memória dinâmica C - C dynamic memory allocation

Biblioteca padrão C
Tópicos gerais
Diversos cabeçalhos

A alocação de memória dinâmica C refere-se à execução de gerenciamento manual de memória para alocação de memória dinâmica na linguagem de programação C por meio de um grupo de funções na biblioteca padrão C , ou seja , malloc , realloc , calloc e free .

A linguagem de programação C ++ inclui essas funções; no entanto, os operadores new e delete fornecem funcionalidade semelhante e são recomendados pelos autores desse idioma. Ainda assim, existem várias situações em que o uso new/deletenão é aplicável, como código de coleta de lixo ou código sensível ao desempenho e uma combinação de malloce placement newpode ser necessária em vez do newoperador de nível superior .

Muitas implementações diferentes do mecanismo real de alocação de memória, usado por malloc , estão disponíveis. Seu desempenho varia em tempo de execução e memória necessária.

Justificativa

A linguagem de programação C gerencia a memória estaticamente , automaticamente ou dinamicamente . Variáveis ​​de duração estática são alocadas na memória principal, geralmente junto com o código executável do programa, e persistem por toda a vida do programa; variáveis ​​de duração automática são alocadas na pilha e vêm e vão conforme as funções são chamadas e retornam. Para variáveis ​​de duração estática e duração automática, o tamanho da alocação deve ser constante de tempo de compilação (exceto para o caso de matrizes automáticas de comprimento variável). Se o tamanho necessário não for conhecido até o tempo de execução (por exemplo, se dados de tamanho arbitrário estiverem sendo lidos do usuário ou de um arquivo de disco), o uso de objetos de dados de tamanho fixo é inadequado.

O tempo de vida da memória alocada também pode causar preocupação. Nem a memória de duração estática nem a automática são adequadas para todas as situações. Os dados alocados automaticamente não podem persistir em várias chamadas de função, enquanto os dados estáticos persistem por toda a vida do programa, sejam necessários ou não. Em muitas situações, o programador requer maior flexibilidade no gerenciamento do tempo de vida da memória alocada.

Essas limitações são evitadas usando a alocação de memória dinâmica , na qual a memória é gerenciada de forma mais explícita (mas mais flexível), normalmente alocando-a do armazenamento gratuito (informalmente chamado de "heap"), uma área de memória estruturada para esse propósito. Em C, a função de biblioteca mallocé usada para alocar um bloco de memória no heap. O programa acessa esse bloco de memória por meio de um ponteiro que mallocretorna. Quando a memória não é mais necessária, o ponteiro é passado para o freequal desaloca a memória para que possa ser usada para outros fins.

A descrição original de C indicava que calloce cfreeestava na biblioteca padrão, mas não malloc. O código para uma implementação de modelo simples de um gerenciador de armazenamento para Unix foi fornecido com alloce freecomo as funções de interface do usuário, e usando a sbrkchamada do sistema para solicitar memória do sistema operacional. A documentação do Unix da 6ª edição fornece alloce freecomo as funções de alocação de memória de baixo nível. As rotinas malloce freeem sua forma moderna são completamente descritas no manual do Unix da 7ª Edição.

Algumas plataformas fornecem bibliotecas ou chamadas de funções intrínsecas que permitem a alocação dinâmica em tempo de execução da pilha C em vez da pilha (por exemplo alloca()). Esta memória é automaticamente liberada quando a função de chamada termina.

Visão geral das funções

As funções de alocação de memória dinâmica C são definidas no stdlib.hcabeçalho ( cstdlibcabeçalho em C ++).

Função Descrição
malloc aloca o número especificado de bytes
realloc aumenta ou diminui o tamanho do bloco de memória especificado, movendo-o se necessário
calloc aloca o número especificado de bytes e os inicializa para zero
free libera o bloco especificado de memória de volta para o sistema

Diferenças entre malloc()ecalloc()

  • malloc()recebe um único argumento (a quantidade de memória a ser alocada em bytes), enquanto calloc()precisa de dois argumentos (o número de variáveis ​​a serem alocadas na memória e o tamanho em bytes de uma única variável).
  • malloc()não inicializa a memória alocada, enquanto calloc()garante que todos os bytes do bloco de memória alocada foram inicializados para 0.
  • Em alguns sistemas operacionais, calloc()pode ser implementado apontando inicialmente todas as páginas dos endereços virtuais da memória alocada para uma página somente leitura de 0s, e apenas alocando páginas físicas de leitura e gravação quando os endereços virtuais são gravados, um método chamado copiar- na gravação .

Exemplo de uso

Criar uma matriz de dez inteiros com escopo automático é simples em C: 

int array[10];

No entanto, o tamanho do array é fixado em tempo de compilação. Se alguém deseja alocar uma matriz semelhante dinamicamente, o seguinte código pode ser usado: 

int *array = (int*)malloc(10 * sizeof(int));

Isso calcula o número de bytes que dez inteiros ocupam na memória, então solicita esses bytes malloce atribui o resultado a um ponteiro chamado array(devido à sintaxe C, ponteiros e matrizes podem ser usados ​​alternadamente em algumas situações).

Como mallocpode não ser capaz de atender à solicitação, ele pode retornar um ponteiro nulo e é uma boa prática de programação verificar isso: 

int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

Quando o programa não precisa mais da matriz dinâmica , ele deve eventualmente chamar freepara retornar a memória que ocupa para o armazenamento gratuito: 

free(array);

A memória reservada por mallocnão é inicializada e pode conter cruft : os restos de dados usados ​​anteriormente e descartados. Após a alocação com malloc, os elementos da matriz são variáveis ​​não inicializadas . O comando callocretornará uma alocação que já foi apagada: 

int *array = calloc(10, sizeof(int));

Com realloc, podemos redimensionar a quantidade de memória para a qual um ponteiro aponta. Por exemplo, se temos um ponteiro atuando como um array de tamanho e queremos alterá-lo para um array de tamanho , podemos usar realloc. 

int *arr = malloc(2 * sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr = realloc(arr, 3 * sizeof(int));
arr[2] = 3;

Observe que realloc deve ser assumido como tendo alterado o endereço base do bloco (ou seja, se ele falhou em estender o tamanho do bloco original e, portanto, alocou um novo bloco maior em outro lugar e copiou o conteúdo antigo nele). Portanto, quaisquer ponteiros para endereços dentro do bloco original também não são mais válidos.

Segurança de tipo

mallocretorna um ponteiro void ( void *), que indica que é um ponteiro para uma região de tipo de dados desconhecido. O uso de conversão é necessário em C ++ devido ao sistema de tipo forte, ao passo que este não é o caso em C. Pode-se "converter" (ver conversão de tipo ) este ponteiro para um tipo específico: 

int *ptr, *ptr2;
ptr = malloc(10 * sizeof(*ptr)); /* without a cast */
ptr2 = (int *)malloc(10 * sizeof(*ptr)); /* with a cast */

Existem vantagens e desvantagens em fazer tal elenco.

Vantagens para fundir

  • Incluir o elenco pode permitir que um programa ou função C compile como C ++.
  • O elenco permite versões pré-1989 do mallocque originalmente retornou a char *.
  • A conversão pode ajudar o desenvolvedor a identificar inconsistências no dimensionamento do tipo caso o tipo de ponteiro de destino mude, especialmente se o ponteiro for declarado longe da malloc()chamada (embora compiladores modernos e analisadores estáticos possam alertar sobre esse comportamento sem exigir a conversão).

Desvantagens do elenco

  • Sob o padrão C, o elenco é redundante.
  • Adicionar o elenco pode mascarar a falha ao incluir o cabeçalho stdlib.h, no qual o protótipo de função para mallocé encontrado. Na ausência de um protótipo para malloc, o padrão C90 requer que o compilador C suponha que mallocretorne um int. Se não houver conversão, C90 exigirá um diagnóstico quando este inteiro for atribuído ao ponteiro; porém, com o elenco, esse diagnóstico não seria produzido, ocultando um bug. Em certas arquiteturas e modelos de dados (como LP64 em sistemas de 64 bits, onde longe os ponteiros são de 64 bits e intsão de 32 bits), esse erro pode realmente resultar em comportamento indefinido, pois o declarado implicitamente mallocretorna um valor de 32 bits, enquanto a função realmente definida retorna um valor de 64 bits. Dependendo das convenções de chamada e do layout da memória, isso pode resultar no esmagamento da pilha . É menos provável que esse problema passe despercebido em compiladores modernos, já que o C99 não permite declarações implícitas, de modo que o compilador deve produzir um diagnóstico mesmo que presuma o intretorno.
  • Se o tipo do ponteiro for alterado em sua declaração, também pode ser necessário alterar todas as linhas onde mallocé chamado e convertido.

Erros comuns

O uso impróprio de alocação dinâmica de memória pode freqüentemente ser uma fonte de bugs. Isso pode incluir bugs de segurança ou travamentos do programa, na maioria das vezes devido a falhas de segmentação .

Os erros mais comuns são os seguintes:

Não verificando falhas de alocação
A alocação de memória não tem garantia de sucesso e, em vez disso, pode retornar um ponteiro nulo. Usar o valor retornado, sem verificar se a alocação foi bem-sucedida, invoca um comportamento indefinido . Isso geralmente leva a um travamento (devido à falha de segmentação resultante na desreferência do ponteiro nulo), mas não há garantia de que um travamento ocorrerá, portanto, confiar nisso também pode levar a problemas.
Perdas de memória
A falha em desalocar memória usando freeleva ao acúmulo de memória não reutilizável, que não é mais usada pelo programa. Isso desperdiça recursos de memória e pode levar a falhas de alocação quando esses recursos se esgotam.
Erros lógicos
Todas as alocações devem seguir o mesmo padrão: uso de alocação malloc, uso para armazenar dados, uso de desalocação free. Falhas em aderir a este padrão, como uso de memória após uma chamada para free( ponteiro pendente ) ou antes de uma chamada para malloc( ponteiro selvagem ), chamar freeduas vezes ("double free"), etc., geralmente causa uma falha de segmentação e resulta em um travamento do programa. Esses erros podem ser transitórios e difíceis de depurar - por exemplo, a memória liberada geralmente não é recuperada imediatamente pelo sistema operacional e, portanto, ponteiros pendentes podem persistir por um tempo e parecer funcionar.

Além disso, como uma interface que precede a padronização ANSI C, malloce suas funções associadas têm comportamentos que foram intencionalmente deixados para a implementação definir por si mesmos. Um deles é a alocação de comprimento zero, que é mais um problema, reallocpois é mais comum redimensionar para zero. Embora POSIX e a Especificação Única do Unix exijam o manuseio adequado de alocações de tamanho 0 por meio do retorno NULLou de outra coisa que possa ser liberada com segurança, nem todas as plataformas precisam obedecer a essas regras. Entre os muitos erros double-free que gerou, o WhatsApp RCE 2019 foi especialmente proeminente. Uma maneira de agrupar essas funções para torná-las mais seguras é simplesmente verificar as alocações de tamanho 0 e transformá-las em tamanhos 1. (Retornar NULLtem seus próprios problemas: caso contrário, indica uma falha de falta de memória. No caso de reallocteria sinalizado que a memória original não foi movida e liberada, o que, novamente, não é o caso para o tamanho 0, levando à liberação dupla.)

Implementações

A implementação do gerenciamento de memória depende muito do sistema operacional e da arquitetura. Alguns sistemas operacionais fornecem um alocador para malloc, enquanto outros fornecem funções para controlar certas regiões de dados. O mesmo alocador de memória dinâmica é freqüentemente usado para implementar ambos malloce o operador newem C ++ .

Baseado em heap

Veja também: sbrk

A implementação do alocador normalmente é feita usando o heap ou segmento de dados . O alocador geralmente expande e contrai o heap para atender às solicitações de alocação.

O método de heap sofre de algumas falhas inerentes, decorrentes inteiramente da fragmentação . Como qualquer método de alocação de memória, o heap ficará fragmentado; ou seja, haverá seções de memória usada e não usada no espaço alocado no heap. Um bom alocador tentará encontrar uma área não utilizada da memória já alocada para usar antes de recorrer à expansão do heap. O principal problema com esse método é que o heap possui apenas dois atributos significativos: base, ou o início do heap no espaço de memória virtual; e comprimento, ou seu tamanho. O heap requer memória de sistema suficiente para preencher todo o seu comprimento e sua base nunca pode ser alterada. Assim, qualquer grande área de memória não utilizada é desperdiçada. O heap pode ficar "preso" nesta posição se um pequeno segmento usado existir no final do heap, o que pode desperdiçar qualquer quantidade de espaço de endereço. Em esquemas de alocação de memória preguiçosos, como aqueles freqüentemente encontrados no sistema operacional Linux, um grande heap não reserva necessariamente a memória de sistema equivalente; ele só fará isso no primeiro tempo de gravação (as leituras de páginas de memória não mapeadas retornam zero). A granularidade disso depende do tamanho da página.

dlmalloc e ptmalloc

Doug Lea desenvolveu o domínio público dlmalloc ("Doug Lea's Malloc") como um alocador de uso geral, a partir de 1987. A biblioteca GNU C (glibc) é derivada do ptmalloc de Wolfram Gloger ("pthreads malloc"), um fork do dlmalloc com melhorias relacionadas ao threading. Em novembro de 2019, a versão mais recente do dlmalloc é a versão 2.8.6 de agosto de 2012.

dlmalloc é um alocador de tags de limite. A memória na pilha é alocada como "blocos", uma estrutura de dados alinhada de 8 bytes que contém um cabeçalho e memória utilizável. A memória alocada contém uma sobrecarga de 8 ou 16 bytes para o tamanho do fragmento e sinalizadores de uso (semelhante a um vetor de droga ). Os pedaços não alocados também armazenam ponteiros para outros pedaços livres na área de espaço utilizável, tornando o tamanho mínimo do pedaço 16 bytes em sistemas de 32 bits e 24/32 (depende do alinhamento) bytes em sistemas de 64 bits.

A memória não alocada é agrupada em " compartimentos " de tamanhos semelhantes, implementados usando uma lista duplamente vinculada de blocos (com ponteiros armazenados no espaço não alocado dentro do bloco). As caixas são classificadas por tamanho em três classes:

  • Para solicitações abaixo de 256 bytes (uma solicitação "smallbin"), um alocador de melhor ajuste de duas potências simples é usado. Se não houver blocos livres nesse compartimento, um bloco do próximo compartimento mais alto será dividido em dois.
  • Para solicitações de 256 bytes ou acima, mas abaixo do limite do mmap , o dlmalloc desde a v2.8.0 usa um algoritmo de trie bit a bit no local ("treebin"). Se não houver espaço livre para atender à solicitação, dlmalloc tentará aumentar o tamanho do heap, geralmente por meio da chamada de sistema brk . Esse recurso foi introduzido logo após a criação do ptmalloc (a partir da v2.7.x) e, como resultado, não faz parte do glibc, que herda o antigo alocador de melhor ajuste.
  • Para solicitações acima do limite mmap (uma solicitação "largebin"), a memória é sempre alocada usando a chamada de sistema mmap . O limite é geralmente de 256 KB. O método mmap evita problemas com buffers enormes prendendo uma pequena alocação no final após sua expiração, mas sempre aloca uma página inteira de memória, que em muitas arquiteturas tem 4096 bytes de tamanho.

O desenvolvedor de jogos Adrian Stone argumenta que dlmalloc, como um alocador de etiqueta de limite, é hostil para sistemas de console que têm memória virtual, mas não têm paginação por demanda . Isso ocorre porque seus callbacks de redução e crescimento de pool (sysmalloc / systrim) não podem ser usados ​​para alocar e confirmar páginas individuais de memória virtual. Na ausência de paginação sob demanda, a fragmentação se torna uma preocupação maior.

FreeBSD's e NetBSD's jemalloc

Desde o FreeBSD 7.0 e o NetBSD 5.0, a mallocimplementação antiga (phkmalloc) foi substituída pelo jemalloc , escrito por Jason Evans. A principal razão para isso foi a falta de escalabilidade do phkmalloc em termos de multithreading. Para evitar contenção de bloqueio, o jemalloc usa "arenas" separadas para cada CPU . Os experimentos que medem o número de alocações por segundo em aplicativos multithreading mostraram que isso o torna uma escala linear com o número de threads, enquanto para phkmalloc e dlmalloc o desempenho era inversamente proporcional ao número de threads.

Malloc do OpenBSD

A implementação da mallocfunção pelo OpenBSD faz uso do mmap . Para solicitações com tamanho superior a uma página, toda a alocação é recuperada usando mmap; tamanhos menores são atribuídos a partir de pools de memória mantidos por mallocdentro de uma série de "páginas de bucket", também alocadas com mmap. Em uma chamada para free, a memória é liberada e não mapeada do espaço de endereço do processo usando munmap. Este sistema é projetado para melhorar a segurança aproveitando a randomização do layout do espaço de endereço e recursos de página de lacuna implementados como parte da mmap chamada do sistema do OpenBSD , e para detectar bugs de uso após a liberação - já que uma grande alocação de memória é completamente desmapeada após ser liberada , o uso posterior causa uma falha de segmentação e o encerramento do programa.

Hoard Malloc

Artigo principal: Alocador de memória Hoard

Hoard é um alocador cujo objetivo é o desempenho de alocação de memória escalonável. Como o alocador do OpenBSD, Hoard usa mmapexclusivamente, mas gerencia a memória em blocos de 64 kilobytes chamados superblocos. O heap do Hoard é logicamente dividido em um único heap global e vários heaps por processador. Além disso, há um cache local de thread que pode conter um número limitado de superblocos. Ao alocar apenas a partir de superblocos no heap local por thread ou por processador e mover superblocos quase vazios para o heap global para que possam ser reutilizados por outros processadores, Hoard mantém a fragmentação baixa enquanto atinge escalabilidade quase linear com o número de threads .

Mimalloc

Artigo principal: mimalloc

Um alocador de memória compacto de propósito geral de código aberto da Microsoft Research com foco no desempenho. A biblioteca tem cerca de 11.000 linhas de código .

Malloc de cache de thread (tcmalloc)

Cada thread tem um armazenamento local de thread para pequenas alocações. Para grandes alocações, mmap ou sbrk podem ser usados. TCMalloc , um malloc desenvolvido pelo Google, tem coleta de lixo para armazenamento local de threads inativos. O TCMalloc é considerado duas vezes mais rápido que o ptmalloc da glibc para programas multithread.

In-kernel

Os kernels do sistema operacional precisam alocar memória da mesma forma que os programas de aplicativos fazem. A implementação de mallocdentro de um kernel geralmente difere significativamente das implementações usadas por bibliotecas C, no entanto. Por exemplo, os buffers de memória podem precisar estar em conformidade com restrições especiais impostas pelo DMA ou a função de alocação de memória pode ser chamada a partir do contexto de interrupção. Isso requer uma mallocimplementação totalmente integrada ao subsistema de memória virtual do kernel do sistema operacional.

Substituindo malloc

Como malloce seus parentes podem ter um forte impacto no desempenho de um programa, não é incomum substituir as funções de um aplicativo específico por implementações customizadas que são otimizadas para os padrões de alocação do aplicativo. O padrão C não fornece nenhuma maneira de fazer isso, mas os sistemas operacionais encontraram várias maneiras de fazer isso explorando a vinculação dinâmica. Uma maneira é simplesmente vincular em uma biblioteca diferente para substituir os símbolos. Outro, empregado pelo Unix System V.3 , é fazer malloce freefuncionar ponteiros que um aplicativo pode redefinir para funções personalizadas.

Limites de tamanho de alocação

O maior bloco de memória possível que mallocpode ser alocado depende do sistema host, principalmente do tamanho da memória física e da implementação do sistema operacional.

Teoricamente, o maior número deve ser o valor máximo que pode ser mantido em um size_ttipo, que é um inteiro não assinado dependente da implementação que representa o tamanho de uma área de memória. No padrão C99 e posterior, está disponível como a SIZE_MAXconstante de <stdint.h>. Embora não seja garantido pelo ISO C , geralmente é . 2^(CHAR_BIT * sizeof(size_t)) - 1

Em sistemas glibc, o maior bloco de memória possível mallocpode alocar tem apenas metade desse tamanho, a saber . 2^(CHAR_BIT * sizeof(ptrdiff_t) - 1) - 1

Extensões e alternativas

As implementações da biblioteca C enviadas com vários sistemas operacionais e compiladores podem vir com alternativas e extensões para a mallocinterface padrão . Entre eles, destacam-se:

  • alloca, que aloca um número solicitado de bytes na pilha de chamadas . Não existe nenhuma função de desalocação correspondente, pois normalmente a memória é desalocada assim que a função de chamada retorna. allocaestava presente em sistemas Unix já em 32 / V (1978), mas seu uso pode ser problemático em alguns contextos (por exemplo, embutidos). Embora seja suportado por muitos compiladores, não faz parte do padrão ANSI-C e, portanto, pode nem sempre ser portátil. Também pode causar pequenos problemas de desempenho: leva a quadros de pilha de tamanho variável, de modo que os ponteiros de pilha e de quadro precisam ser gerenciados (com quadros de pilha de tamanho fixo, um deles é redundante). Alocações maiores também podem aumentar o risco de comportamento indefinido devido a um estouro de pilha . O C99 ofereceu arrays de comprimento variável como um mecanismo alternativo de alocação de pilha - no entanto, esse recurso foi relegado a opcional no padrão C11 posterior .
  • POSIX define uma função posix_memalignque aloca memória com alinhamento especificado pelo chamador. Suas alocações são desalocadas com free, portanto, a implementação geralmente precisa fazer parte da biblioteca malloc.

Veja também

Referências

links externos