Como malloc () e free () funcionam?

Eu quero saber como malloce freetrabalhar.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Ficaria muito grato se a resposta estiver em profundidade no nível da memória, se for possível.

OK, algumas respostas sobre o malloc já foram publicadas.

A parte mais interessante é como o free funciona (e nessa direção, o malloc também pode ser melhor entendido).

Em muitas implementações malloc / free, free normalmente não retorna a memória para o sistema operacional (ou pelo menos apenas em casos raros). O motivo é que você terá lacunas na pilha e, assim, pode acontecer, que você acaba com 2 ou 4 GB de memória virtual com lacunas. Isso deve ser evitado, pois assim que a memória virtual terminar, você terá um grande problema. A outra razão é que o sistema operacional pode lidar apenas com pedaços de memória com tamanho e alinhamento específicos. Para ser específico: Normalmente, o sistema operacional pode lidar apenas com blocos que o gerenciador de memória virtual pode lidar (geralmente múltiplos de 512 bytes, por exemplo, 4KB).

Portanto, retornar 40 bytes ao sistema operacional simplesmente não funcionará. Então, o que o livre faz?

O Free colocará o bloco de memória em sua própria lista de bloqueios gratuitos. Normalmente, ele também tenta mesclar blocos adjacentes no espaço de endereço. A lista de bloqueios gratuitos é apenas uma lista circular de blocos de memória que possuem alguns dados administrativos no início. Esse também é o motivo pelo qual o gerenciamento de elementos de memória muito pequenos com o malloc / free padrão não é eficiente. Cada pedaço de memória precisa de dados adicionais e, com tamanhos menores, ocorre mais fragmentação.

A lista livre também é o primeiro lugar que o malloc analisa quando é necessário um novo pedaço de memória. Ele é verificado antes de solicitar nova memória do sistema operacional. Quando um pedaço é maior que a memória necessária, ele é dividido em duas partes. Um é retornado ao chamador, o outro é colocado de volta na lista gratuita.

Há muitas otimizações diferentes para esse comportamento padrão (por exemplo, pequenos pedaços de memória). Porém, como malloc e free devem ser tão universais, o comportamento padrão é sempre o substituto quando as alternativas não são utilizáveis. Também há otimizações no manuseio da lista livre - por exemplo, armazenando os chunks em listas classificadas por tamanhos. Mas todas as otimizações também têm suas próprias limitações.

Por que seu código falha:

O motivo é que, ao escrever 9 caracteres (não esqueça o byte nulo à direita) em uma área dimensionada para 4 caracteres, você provavelmente substituirá os dados administrativos armazenados em outro pedaço de memória que fica "atrás" do seu pedaço de dados ( já que esses dados costumam ser armazenados "na frente" dos blocos de memória). Quando o free tenta colocar seu pedaço na lista gratuita, ele pode tocar esses dados administrativos e, portanto, tropeçar em um ponteiro substituído. Isso irá travar o sistema.

Este é um comportamento bastante gracioso. Também vi situações em que um ponteiro fugitivo em algum lugar substituiu dados na lista sem memória e o sistema não travou imediatamente, mas algumas sub-rotinas posteriormente. Mesmo em um sistema de média complexidade, esses problemas podem ser muito, muito difíceis de depurar! No primeiro caso em que participei, levamos (um grupo maior de desenvolvedores) vários dias para descobrir o motivo do travamento - já que ele estava em um local totalmente diferente daquele indicado pelo despejo de memória. É como uma bomba-relógio. Você sabe, seu próximo "grátis" ou "malloc" falhará, mas você não sabe o porquê!

Esses são alguns dos piores problemas de C / C ++ e uma das razões pelas quais os ponteiros podem ser tão problemáticos.

Como o aluser diz neste tópico do fórum :

Seu processo possui uma região de memória, do endereço x ao endereço y, chamado heap. Todos os seus dados de malloc'd residem nessa área. malloc () mantém alguma estrutura de dados, digamos uma lista, de todos os pedaços livres de espaço no heap. Quando você liga para malloc, ele procura na lista um pedaço grande o suficiente para você, retorna um ponteiro para ele e registra o fato de que ele não é mais gratuito e o tamanho dele. Quando você chama free () com o mesmo ponteiro, free () consulta o tamanho desse pedaço e o adiciona de volta à lista de pedaços livres (). Se você chamar malloc () e ele não encontrar nenhum pedaço grande o suficiente no heap, ele usará o syscall brk () para aumentar o heap, ou seja, aumente o endereço y e faça com que todos os endereços entre o y antigo e o novo y sejam ser memória válida. brk () deve ser um syscall;

malloc () depende do sistema / compilador, por isso é difícil dar uma resposta específica. Basicamente, no entanto, ele monitora a memória que está alocada e, dependendo de como o faz, suas chamadas para liberar podem falhar ou obter êxito.

malloc() and free() don't work the same way on every O/S.

Uma implementação do malloc / free faz o seguinte:

1. Obtenha um bloco de memória do sistema operacional por meio de sbrk () (chamada Unix).
2. Crie um cabeçalho e rodapé em torno desse bloco de memória com algumas informações como tamanho, permissões e onde estão o bloco seguinte e o anterior.
3. Quando uma chamada para malloc é recebida, é mencionada uma lista que aponta para blocos do tamanho apropriado.
4. Esse bloco é retornado e os cabeçalhos e rodapés são atualizados de acordo.

A proteção de memória possui granularidade de página e exigiria interação do kernel

Seu código de exemplo pergunta essencialmente por que o programa de exemplo não intercepta e a resposta é que a proteção de memória é um recurso do kernel e se aplica apenas a páginas inteiras, enquanto o alocador de memória é um recurso de biblioteca e gerencia .. sem imposição .. arbitrário blocos de tamanho que geralmente são muito menores que as páginas.

A memória só pode ser removida do seu programa em unidades de páginas e é improvável que isso seja observado.

calloc (3) e malloc (3) interagem com o kernel para obter memória, se necessário. Mas a maioria das implementações do free (3) não retorna a memória para o kernel ¹ , apenas a adiciona a uma lista livre que calloc () e malloc () consultam mais tarde para reutilizar os blocos liberados.

Mesmo que um free () quisesse retornar memória ao sistema, seria necessário pelo menos uma página de memória contígua para conseguir que o kernel realmente protegesse a região, então liberar um pequeno bloco só levaria a uma alteração na proteção se fosse o último pequeno bloco de uma página.

Portanto, seu bloco está lá, sentado na lista gratuita. Você quase sempre pode acessá-lo e a memória próxima, como se ainda estivesse alocada. C compila diretamente para o código da máquina e sem acordos especiais de depuração, não há verificações de sanidade nas cargas e lojas. Agora, se você tentar acessar um bloco livre, o comportamento será indefinido pelo padrão para não fazer exigências irracionais aos implementadores de bibliotecas. Se você tentar acessar a memória ou memória liberada fora de um bloco alocado, há várias coisas que podem dar errado:

• Às vezes, os alocadores mantêm blocos de memória separados, às vezes eles usam um cabeçalho que eles alocam antes ou depois (um "rodapé", eu acho)) do seu bloco, mas eles podem querer usar a memória dentro do bloco para manter a lista livre ligados em conjunto. Nesse caso, sua leitura do bloco está OK, mas seu conteúdo pode mudar, e a gravação no bloco provavelmente fará com que o alocador se comporte de forma incorreta ou trave.
• Naturalmente, seu bloco poderá ser alocado no futuro e, provavelmente, será substituído pelo seu código ou rotina de biblioteca ou com zeros por calloc ().
• Se o bloco for realocado, ele também poderá ter seu tamanho alterado. Nesse caso, mais links ou inicialização serão gravados em vários locais.
• Obviamente, você pode fazer uma referência tão fora do alcance que cruza um limite de um dos segmentos conhecidos do kernel do seu programa e, nesse caso, irá interceptar.

Teoria de Operação

Portanto, trabalhando de trás para frente, do exemplo à teoria geral, o malloc (3) obtém memória do kernel quando necessário, e normalmente em unidades de páginas. Essas páginas são divididas ou consolidadas conforme o programa exige. Malloc e free cooperam para manter um diretório. Eles coalescem blocos livres adjacentes quando possível para poder fornecer blocos grandes. O diretório pode ou não envolver o uso da memória em blocos liberados para formar uma lista vinculada. (A alternativa é um pouco mais de memória compartilhada e amigável para paginação, e envolve alocar memória especificamente para o diretório.) Malloc e free têm pouca ou nenhuma capacidade de impor o acesso a blocos individuais, mesmo quando o código de depuração especial e opcional é compilado no o programa.

^{1. O fato de pouquíssimas implementações de free () tentarem devolver memória ao sistema não é necessariamente devido à falta de implementadores. Interagir com o kernel é muito mais lento do que simplesmente executar o código da biblioteca, e o benefício seria pequeno. Como a maioria dos programas tem um estado estacionário ou aumento da pegada de memória, o tempo gasto analisando o heap procurando memória retornável seria completamente desperdiçado. Outras razões incluem o fato de que a fragmentação interna torna improvável a existência de blocos alinhados à página, e é provável que o retorno de um bloco fragmente os blocos para ambos os lados. Finalmente, os poucos programas que retornam grandes quantidades de memória provavelmente ignoram malloc () e simplesmente alocam e liberam páginas de qualquer maneira.}

Em teoria, o malloc obtém memória do sistema operacional para este aplicativo. No entanto, como você pode querer apenas 4 bytes e o sistema operacional precisa funcionar em páginas (geralmente 4k), o malloc faz um pouco mais do que isso. Ele pega uma página e coloca suas próprias informações para que ele possa acompanhar o que você alocou e liberou dessa página.

Quando você aloca 4 bytes, por exemplo, o malloc fornece um ponteiro para 4 bytes. O que você pode não perceber é que a memória de 8 a 12 bytes antes dos 4 bytes está sendo usada pelo malloc para criar uma cadeia de toda a memória que você alocou. Quando você liga grátis, ele pega o ponteiro, faz o backup para onde estão os dados e opera com base nisso.

Quando você libera memória, o malloc retira esse bloco de memória da cadeia ... e pode ou não devolver essa memória ao sistema operacional. Nesse caso, o acesso a essa memória provavelmente falhará, pois o sistema operacional retirará suas permissões para acessar esse local. Se o malloc mantiver a memória (porque há outras coisas alocadas nessa página ou para alguma otimização), o acesso funcionará. Ainda está errado, mas pode funcionar.

AVISO LEGAL: O que descrevi é uma implementação comum do malloc, mas de maneira alguma a única possível.

Sua linha strcpy tenta armazenar 9 bytes, não 8, por causa do terminador NUL. Invoca um comportamento indefinido.

A chamada para liberar pode ou não travar. A memória "depois" dos 4 bytes da sua alocação pode ser usada para outra coisa pela sua implementação C ou C ++. Se for usado para outra coisa, rabiscar por toda parte fará com que essa "outra coisa" dê errado, mas se não for usada para mais nada, você poderá se safar. "Fugir com isso" pode parecer bom, mas na verdade é ruim, pois significa que seu código parecerá funcionar bem, mas em uma execução futura você poderá não se safar.

Com um alocador de memória no estilo de depuração, você pode achar que um valor de proteção especial foi gravado lá e que a verificação gratuita desse valor e entra em pânico se não o encontrar.

Caso contrário, você poderá descobrir que os próximos 5 bytes incluem parte de um nó de link pertencente a algum outro bloco de memória que ainda não foi alocado. A liberação do seu bloco poderia muito bem envolvê-lo em uma lista de blocos disponíveis e, como você rabiscou no nó da lista, essa operação pode desreferenciar um ponteiro com um valor inválido, causando uma falha.

Tudo depende do alocador de memória - implementações diferentes usam mecanismos diferentes.

O funcionamento do malloc () e free () depende da biblioteca de tempo de execução usada. Geralmente, malloc () aloca um heap (um bloco de memória) do sistema operacional. Cada solicitação para malloc () aloca um pequeno pedaço dessa memória retornando um ponteiro para o chamador. As rotinas de alocação de memória precisarão armazenar algumas informações extras sobre o bloco de memória alocado para poder controlar a memória usada e liberar a pilha. Essas informações geralmente são armazenadas em alguns bytes antes do ponteiro retornado por malloc () e podem ser uma lista vinculada de blocos de memória.

Ao escrever além do bloco de memória alocado por malloc (), você provavelmente destruirá algumas das informações contábeis do próximo bloco, que podem ser o bloco de memória restante não utilizado.

Um local em que você programa pode também falhar é ao copiar muitos caracteres no buffer. Se os caracteres extras estiverem localizados fora da pilha, você poderá obter uma violação de acesso enquanto estiver tentando gravar na memória não existente.

Isso não tem nada a ver especificamente com malloc e grátis. Seu programa exibe um comportamento indefinido depois que você copia a sequência - ela pode falhar nesse momento ou a qualquer momento depois. Isso seria verdade mesmo se você nunca usasse malloc e free e alocasse a matriz char na pilha ou estaticamente.

malloc e free dependem da implementação. Uma implementação típica envolve particionar a memória disponível em uma "lista livre" - uma lista vinculada de blocos de memória disponíveis. Muitas implementações o dividem artificialmente em objetos pequenos vs grandes. Os blocos livres começam com informações sobre o tamanho do bloco de memória, onde fica o próximo, etc.

Quando você faz compras, um bloco é retirado da lista gratuita. Quando você libera, o bloco é colocado de volta na lista gratuita. As chances são de que, quando você sobrescreve o final do ponteiro, está escrevendo no cabeçalho de um bloco na lista gratuita. Quando você libera sua memória, free () tenta olhar para o próximo bloco e provavelmente acaba atingindo um ponteiro que causa um erro no barramento.

Bem, isso depende da implementação do alocador de memória e do sistema operacional.

Nas janelas, por exemplo, um processo pode solicitar uma página ou mais de RAM. O sistema operacional atribui essas páginas ao processo. No entanto, isso não é memória alocada para o seu aplicativo. O alocador de memória CRT marcará a memória como um bloco "disponível" contíguo. O alocador de memória CRT percorre a lista de blocos livres e encontra o menor bloco possível que ele pode usar. Ele pegará o bloco necessário e o adicionará a uma lista "alocada". Anexado ao cabeçalho da alocação de memória real, haverá um cabeçalho. Este cabeçalho conterá várias informações (pode, por exemplo, conter os blocos alocados seguintes e anteriores para formar uma lista vinculada. Provavelmente conterá o tamanho da alocação).

O Free removerá o cabeçalho e o adicionará novamente à lista de memória livre. Se formar um bloco maior com os blocos livres ao redor, eles serão adicionados para criar um bloco maior. Se uma página inteira estiver agora livre, o alocador provavelmente retornará a página ao sistema operacional.

Não é um problema simples. A parte do alocador do SO está completamente fora de seu controle. Eu recomendo que você leia algo como o Malloc de Doug Lea (DLMalloc) para entender como um alocador razoavelmente rápido funcionará.

Editar: sua falha será causada pelo fato de que, ao escrever maior que a alocação, você substituiu o próximo cabeçalho de memória. Dessa maneira, quando liberada, fica muito confuso quanto ao que exatamente é liberado e como mesclar no bloco a seguir. Isso nem sempre pode causar um acidente imediatamente de graça. Pode causar um travamento mais tarde. Em geral, evite substituições de memória!

Seu programa falha porque usou memória que não pertence a você. Pode ser usado por outra pessoa ou não - se você tiver sorte, falha, se não o problema pode permanecer oculto por um longo tempo e voltar e morder você mais tarde.

No que diz respeito à implementação malloc / free - livros inteiros são dedicados ao tópico. Basicamente, o alocador obteria maiores pedaços de memória do sistema operacional e os gerenciaria para você. Alguns dos problemas que um alocador deve resolver são:

• Como obter nova memória
• Como armazená-lo - (lista ou outra estrutura, várias listas de blocos de memória de tamanhos diferentes e assim por diante)
• O que fazer se o usuário solicitar mais memória do que o disponível no momento (solicite mais memória do SO, junte-se a alguns dos blocos existentes, como juntá-los exatamente, ...)
• O que fazer quando o usuário libera memória
• Os alocadores de depuração podem fornecer um pedaço maior que você solicitou e preenchê-lo com algum padrão de bytes. Quando você libera a memória, o alocador pode verificar se gravou fora do bloco (o que provavelmente está acontecendo no seu caso) ...

É difícil dizer porque o comportamento real é diferente entre diferentes compiladores / tempos de execução. Até versões de depuração / lançamento têm comportamento diferente. As compilações de depuração do VS2005 inserem marcadores entre as alocações para detectar corrupção de memória; portanto, em vez de uma falha, ele será declarado em free ().

Também é importante perceber que, simplesmente movendo o ponteiro de interrupção do programa brke sbrknão alocando a memória, ele apenas configura o espaço de endereço. No Linux, por exemplo, a memória será "suportada" por páginas físicas reais quando esse intervalo de endereços for acessado, o que resultará em uma falha de página e, eventualmente, levará o kernel a chamar o alocador de páginas para obter uma página de backup.