Como o free sabe quanto liberar?

385

Na programação C, você pode transmitir qualquer tipo de ponteiro que desejar como argumento para liberar, como ele sabe o tamanho da memória alocada para liberar? Sempre que passo um ponteiro para alguma função, também preciso passar o tamanho (ou seja, uma matriz de 10 elementos precisa receber 10 como parâmetro para saber o tamanho da matriz), mas não preciso passar o tamanho para o função livre. Por que não, e posso usar essa mesma técnica em minhas próprias funções para evitar que eu precise carregar a variável extra do comprimento da matriz?

Joshua Cheek
fonte
Uma pergunta semelhante: stackoverflow.com/questions/851958/... (embora eu diria que ele não está muito duplicar)
John Carter
O sistema de amigos é outra maneira de fazer isso, que pode ser calculada com base no ponteiro, sem sobrecarga em cada bloco.
21714 EvilTeach
Este post explica bem: stackoverflow.com/questions/1957099/…
Zeeshan Mahmood

Respostas:

349

Ao ligar malloc(), você especifica a quantidade de memória a alocar. A quantidade de memória realmente usada é um pouco mais do que isso e inclui informações extras que registram (pelo menos) o tamanho do bloco. Você não pode (de forma confiável) acessar essas outras informações - e nem deve :-).

Quando você liga free(), simplesmente analisa as informações extras para descobrir o tamanho do bloco.

Gary McGill
fonte
44
Para sua informação, por exemplo, o BSD precisa malloc_size()acessar de forma confiável o tamanho do bloco a partir de um malloc()ponteiro ed. Mas não há uma maneira confiável e portátil.
laalto
50
Eu acho que é importante dizer que esse bloco de informações extras está situado antes do ponteiro retornado.
Georg Schölly 5/10/09
39
@gs Bem, isso depende da implementação. Mas sim, é onde costuma estar.
Falaina 5/10/09
31
Você pode imaginar o horror, se free()exigido que o programador relate com precisão o tamanho do malloc()bloco? Os vazamentos de memória já são ruins o suficiente.
MusiGenesis
35
Por que essas informações estão disponíveis para malloc()e free(), mas você precisa armazenar o tamanho de uma matriz? Por que eles não tornariam possível fazer algo como blockSize(ptr)se estivessem armazenando as informações de qualquer maneira?
corsiKa
144

A maioria das implementações das funções de alocação de memória C armazenará informações contábeis para cada bloco, em linha ou separadamente.

Uma maneira típica (em linha) é realmente alocar o cabeçalho e a memória solicitada, preenchidos com algum tamanho mínimo. Por exemplo, se você solicitou 20 bytes, o sistema pode alocar um bloco de 48 bytes:

  • Cabeçalho de 16 bytes contendo tamanho, marcador especial, soma de verificação, ponteiros para o bloco seguinte / anterior e assim por diante.
  • Área de dados de 32 bytes (seus 20 bytes aumentam para um múltiplo de 16).

O endereço então fornecido a você é o endereço da área de dados. Então, quando você liberar o bloco, freesimplesmente pegará o endereço que você deu e, supondo que você não tenha enchido o endereço ou a memória em torno dele, verifique as informações contábeis imediatamente antes dele. Graficamente, isso seria ao longo das linhas de:

 ____ The allocated block ____
/                             \
+--------+--------------------+
| Header | Your data area ... |
+--------+--------------------+
          ^
          |
          +-- The address you are given

Lembre-se de que o tamanho do cabeçalho e o preenchimento são totalmente definidos pela implementação (na verdade, a coisa toda é definida pela implementação (a), mas a opção de contabilidade em linha é comum).

As somas de verificação e marcadores especiais que existem nas informações contábeis geralmente causam erros como "Arena de memória corrompida" ou "Liberação dupla" se você as substituir ou liberar duas vezes.

O preenchimento (para tornar a alocação mais eficiente) é o motivo pelo qual você pode escrever um pouco além do final do espaço solicitado sem causar problemas (ainda assim, não faça isso, é um comportamento indefinido e, só porque funciona às vezes, não funciona) significa que não há problema em fazê-lo).


(a) Eu escrevi implementações mallocem sistemas embarcados em que você obteve 128 bytes, independentemente do que solicitou (que era o tamanho da maior estrutura do sistema), supondo que você solicitasse 128 bytes ou menos (solicitações de mais seja atendido com um valor de retorno NULL). Uma máscara de bits muito simples (isto é, não alinhada) foi usada para decidir se um pedaço de 128 bytes foi alocado ou não.

Outros que desenvolvi tinham pools diferentes para blocos de 16 bytes, blocos de 64 bytes, blocos de 256 bytes e blocos de 1K, novamente usando uma máscara de bits para decidir quais blocos eram usados ​​ou disponíveis.

Ambas as opções conseguiram reduzir a sobrecarga das informações contábeis e aumentar a velocidade malloce free(não há necessidade de coalescer blocos adjacentes ao liberar), particularmente importante no ambiente em que estávamos trabalhando.

paxdiablo
fonte
@paxdiablo Isso significa que o malloc não aloca blocos contíguos de memória?
user10678
2
@ user10678, o único requisito real mallocé fornecer, para o caso de sucesso, um bloco de memória pelo menos tão grande quanto o que você solicitou. Blocos individuais são contíguos em termos de como você acessa elementos dentro deles, mas não é necessário que as arenas de onde os blocos vêm sejam contíguas.
precisa
Pergunta relacionada: Por que não há variação de malloc / free, onde você especifica o tamanho ao liberar e, portanto, não precisa armazenar o tamanho?
user253751
@ user253751, porque então é mais uma coisa que você precisa acompanhar, acima e acima do ponteiro. É desnecessário e perigoso: void *x = malloc(200); free(x, 500);é não vai acabar bem :-) Em qualquer caso, para a eficiência, o real tamanho do buffer pode ser maior (você só não pode contar com isso).
paxdiablo
@paxdiablo Também evita o desperdício de memória para manter o tamanho.
user253751
47

Na comp.lang.clista de perguntas frequentes: como o free sabe quantos bytes o free?

A implementação malloc / free lembra o tamanho de cada bloco à medida que é alocado, portanto, não é necessário lembrá-lo do tamanho ao liberar. (Normalmente, o tamanho é armazenado adjacente ao bloco alocado, e é por isso que as coisas geralmente quebram mal se os limites do bloco alocado são levemente ultrapassados)

jdehaan
fonte
2
Esta é uma não resposta. A questão é exatamente esta: por que o Free pode procurar com confiança o tamanho do bloco, mas ainda assim não há nenhuma função disponível para o programador que faz isso?
Bananach 4/01/19
Este é realmente um detalhe de implementação da API malloc e não existe uma API para recuperar essas informações de maneira padrão (que eu saiba). O "sistema" registra e usa isso free. Talvez a resposta não é satisfatória você, mas eu não acho que você vai ter um com mais informações genericamente aplicável :-)
jdehaan
6

Esta resposta é realocada em Como free () sabe quanta memória desalocar? onde fui abruptamente impedido de responder por uma pergunta duplicada aparente. Esta resposta deve ser relevante para esta duplicata:


No caso de malloc, o alocador de heap armazena um mapeamento do ponteiro retornado original, para detalhes relevantes necessários para freea memória posteriormente. Isso geralmente envolve o armazenamento do tamanho da região da memória em qualquer forma relevante para o alocador em uso, por exemplo, tamanho bruto ou um nó em uma árvore binária usada para rastrear alocações ou uma contagem de "unidades" de memória em uso.

freenão falhará se você "renomear" o ponteiro ou duplicá-lo de qualquer forma. No entanto, não é contada a referência e apenas a primeira freeestará correta. freeS adicionais são erros "duplos".

Tentativa de freequalquer ponteiro com um valor diferente dos retornados por mallocs anteriores e ainda não liberada é um erro. Não é possível liberar parcialmente as regiões de memória retornadas malloc.

Matt Joiner
fonte
Alterei o valor de um ponteiro retornado por uma chamada de malloc. E eu o soltei sem erro. Por quê? Veja aqui: stackoverflow.com/questions/42618390/…
smwikipedia 6/17
4

Em uma nota relacionada, a biblioteca GLib possui funções de alocação de memória que não salvam o tamanho implícito - e você passa o parâmetro size para liberar. Isso pode eliminar parte da sobrecarga.

EFraim
fonte
3

malloc()e free()dependem do sistema / compilador, por isso é difícil dar uma resposta específica.

Mais informações sobre essa outra questão .

LiraNuna
fonte
2
Eles são realmente dependentes da biblioteca (normalmente a biblioteca C, que geralmente está intimamente ligada ao sistema operacional). Para o compilador, são apenas funções.
Donal Fellows
2

O gerenciador de heap armazenou a quantidade de memória pertencente ao bloco alocado em algum lugar quando você ligou malloc.

Eu nunca implementei um, mas acho que a memória bem na frente do bloco alocado pode conter as meta informações.

Timbó
fonte
3
Essa é uma implementação possível, mas é possível criar um sistema em que toda a memória seja rastreada em uma única tabela em uma página totalmente diferente, não necessariamente em qualquer lugar próximo ao pool de memória que está sendo alocado.
ephemient
2

A técnica original era alocar um bloco um pouco maior e armazenar o tamanho no início e depois dar ao aplicativo o resto do blog. O espaço extra possui um tamanho e, possivelmente, links para encadear os blocos livres para reutilização.

Existem alguns problemas com esses truques, no entanto, como mau comportamento do cache e do gerenciamento de memória. O uso da memória no bloco tende a paginar as coisas desnecessariamente e também cria páginas sujas que complicam o compartilhamento e a cópia na gravação.

Portanto, uma técnica mais avançada é manter um diretório separado. Abordagens exóticas também foram desenvolvidas onde áreas da memória usam o mesmo tamanho de dois tamanhos.

Em geral, a resposta é: uma estrutura de dados separada é alocada para manter o estado.

DigitalRoss
fonte
1

Para responder à segunda metade da sua pergunta: sim, você pode, e um padrão bastante comum em C é o seguinte:

typedef struct {
    size_t numElements
    int elements[1]; /* but enough space malloced for numElements at runtime */
} IntArray_t;

#define SIZE 10
IntArray_t* myArray = malloc(sizeof(intArray_t) + SIZE * sizeof(int));
myArray->numElements = SIZE;
MSalters
fonte
Essa é uma técnica completamente diferente para os usos malloc um BSD para pequenos objectos (apesar de ser um perfeitamente boa técnica para a criação de matrizes de estilo Pascal)
Pete Kirkham
0

Quando chamamos malloc, ele simplesmente consome mais bytes do que é requisito. Esse consumo de mais bytes contém informações como soma de verificação, tamanho e outras informações adicionais. Quando ligamos gratuitamente naquele momento, ele acessa diretamente as informações adicionais, onde encontra o endereço e também descobre quanto bloco será gratuito.

Varun Chhangani
fonte
0

Para responder à segunda pergunta, sim, você poderia (mais ou menos) usar a mesma técnica, malloc() simplesmente atribuindo a primeira célula dentro de cada matriz ao tamanho da matriz. que permite enviar a matriz sem enviar um argumento de tamanho adicional.

avish
fonte