(Nessun controllo è spiegato in questo riassunto e alcuni casi sono stati omessi per brevità)
__libc_malloc cerca di ottenere un chunk dalla tcache, se non riesce chiama _int_malloc
_int_malloc :
Cerca di generare l'arena se non ce n'è nessuna
Se c'è un chunk fast bin della dimensione corretta, lo usa
Riempie la tcache con altri chunk fast
Se c'è un chunk small bin della dimensione corretta, lo usa
Riempie la tcache con altri chunk di quella dimensione
Se la dimensione richiesta non è per i small bin, consolidare il fast bin nell'unsorted bin
Controlla l'unsorted bin, usa il primo chunk con abbastanza spazio
Se il chunk trovato è più grande, dividilo per restituire una parte e aggiungi il resto all'unsorted bin
Se un chunk è della stessa dimensione della dimensione richiesta, usalo per riempire la tcache invece di restituirlo (fino a quando la tcache è piena, quindi restituisci il successivo)
Per ogni chunk di dimensione più piccola controllato, mettilo nel rispettivo small o large bin
Controlla il large bin nell'indice della dimensione richiesta
Inizia a cercare dal primo chunk più grande della dimensione richiesta, se ne trovi uno restituiscilo e aggiungi i resti al small bin
Controlla i large bin dai prossimi indici fino alla fine
Dal prossimo indice più grande controlla per eventuali chunk, divide il primo chunk trovato per usarlo per la dimensione richiesta e aggiungi il resto all'unsorted bin
Se non viene trovato nulla nei bin precedenti, ottieni un chunk dal chunk superiore
Se il chunk superiore non era abbastanza grande, ingrandiscilo con sysmalloc
__libc_malloc
La funzione malloc effettivamente chiama __libc_malloc. Questa funzione controlla la tcache per vedere se c'è un chunk disponibile della dimensione desiderata. Se c'è, lo userà e se non c'è, verificherà se è un singolo thread e in tal caso chiamerà _int_malloc nell'arena principale e, se non lo è, chiamerà _int_malloc nell'arena del thread.
Codice di __libc_malloc
```c // From https://github.com/bminor/glibc/blob/master/malloc/malloc.c
victim = _int_malloc (ar_ptr, bytes); /* Retry with another arena only if we were able to find a usable arena before. */ if (!victim && ar_ptr != NULL) { LIBC_PROBE (memory_malloc_retry, 1, bytes); ar_ptr = arena_get_retry (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes); }
if (ar_ptr != NULL) __libc_lock_unlock (ar_ptr->mutex);
</details>
Nota come etichetterà sempre il puntatore restituito con `tag_new_usable`, dal codice:
```c
void *tag_new_usable (void *ptr)
Allocate a new random color and use it to color the user region of
a chunk; this may include data from the subsequent chunk's header
if tagging is sufficiently fine grained. Returns PTR suitably
recolored for accessing the memory there.
_int_malloc
Questa è la funzione che alloca memoria utilizzando gli altri blocchi e il chunk superiore.
Inizio
Inizia definendo alcune variabili e ottenendo la dimensione reale di spazio di memoria richiesta che deve avere:
Fast Bin
Se la dimensione necessaria è all'interno delle dimensioni dei Fast Bins, prova a utilizzare un chunk dal fast bin. Fondamentalmente, in base alla dimensione, troverà l'indice del fast bin in cui dovrebbero trovarsi i chunk validi e, se ce ne sono, restituirà uno di quelli.
Inoltre, se la tcache è abilitata, riempirà il tcache bin di quella dimensione con i fast bin.
Durante l'esecuzione di queste azioni, vengono eseguiti alcuni controlli di sicurezza qui:
Se il chunk non è allineato: malloc(): rilevato chunk fastbin non allineato 2
Se il chunk successivo non è allineato: malloc(): rilevato chunk fastbin non allineato
Se il chunk restituito ha una dimensione non corretta a causa del suo indice nel fast bin: malloc(): corruzione della memoria (fast)
Se un qualsiasi chunk utilizzato per riempire la tcache non è allineato: malloc(): rilevato chunk fastbin non allineato 3
malloc_consolidate
Se non si trattava di un piccolo chunk, si tratta di un grande chunk e, in questo caso, viene chiamato malloc_consolidate per evitare la frammentazione della memoria.
Unsorted bin
È il momento di controllare il bin non ordinato per individuare un possibile chunk valido da utilizzare.
Inizio
Questo inizia con un grande ciclo che attraverserà il bin non ordinato nella direzione bk fino a quando non arriva alla fine (la struttura dell'arena) con while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
Inoltre, vengono eseguiti alcuni controlli di sicurezza ogni volta che viene considerato un nuovo chunk:
Se le dimensioni del chunk sono strane (troppo piccole o troppo grandi): malloc(): dimensione non valida (non ordinato)
Se le dimensioni del chunk successivo sono strane (troppo piccole o troppo grandi): malloc(): dimensione successiva non valida (non ordinato)
Se le dimensioni precedenti indicate dal chunk successivo differiscono dalle dimensioni del chunk: malloc(): dimensioni next->prev non corrispondenti (non ordinato)
Se non victim->bck->fd == victim o non victim->fd == av (arena): malloc(): lista doppiamente collegata non ordinata corrotta
Poiché stiamo sempre controllando l'ultimo, il suo fd dovrebbe puntare sempre alla struttura dell'arena.
Se il chunk successivo non indica che il precedente è in uso: malloc(): next->prev_inuse non valido (non ordinato)
Se ciò è avvenuto con successo, restituisci il chunk e termina, altrimenti continua ad eseguire la funzione...
se le dimensioni sono uguali
Continua a rimuovere il chunk dal bin, nel caso in cui la dimensione richiesta sia esattamente quella del chunk:
Se il tcache non è pieno, aggiungilo al tcache e continua a indicare che c'è un chunk tcache che potrebbe essere utilizzato
Se il tcache è pieno, usalo semplicemente restituendolo
```c // From https://github.com/bminor/glibc/blob/master/malloc/malloc.c#L4227C1-L4250C7
#if USE_TCACHE /* If we've processed as many chunks as we're allowed while filling the cache, return one of the cached ones. */ ++tcache_unsorted_count; if (return_cached && mp_.tcache_unsorted_limit > 0 && tcache_unsorted_count > mp_.tcache_unsorted_limit) { return tcache_get (tc_idx); } #endif
#define MAX_ITERS 10000 if (++iters >= MAX_ITERS) break; }
#if USE_TCACHE /* If all the small chunks we found ended up cached, return one now. */ if (return_cached) { return tcache_get (tc_idx); } #endif
</details>
Se i limiti non sono stati raggiunti, continua con il codice...
### Large Bin (per indice)
Se la richiesta è grande (non è nella small bin) e non abbiamo ancora restituito alcun chunk, otteniamo l'**indice** della dimensione richiesta nel **large bin**, controlliamo se **non è vuoto** o se il **chunk più grande in questo bin è più grande** della dimensione richiesta e in tal caso troviamo il **chunk più piccolo che può essere utilizzato** per la dimensione richiesta.
Se lo spazio rimanente dal chunk utilizzato alla fine può essere un nuovo chunk, aggiungilo al unsorted bin e l'ultimo\_reminder viene aggiornato.
Viene effettuato un controllo di sicurezza quando si aggiunge il reminder all'unsorted bin:
* `bck->fd-> bk != bck`: `malloc(): chunk non ordinati corrotti`
<details>
<summary><code>_int_malloc</code> Large bin (per indice)</summary>
```c
// From https://github.com/bminor/glibc/blob/master/malloc/malloc.c#L4252C7-L4317C10
/*
If a large request, scan through the chunks of current bin in
sorted order to find smallest that fits. Use the skip list for this.
*/
if (!in_smallbin_range (nb))
{
bin = bin_at (av, idx);
/* skip scan if empty or largest chunk is too small */
if ((victim = first (bin)) != bin
&& (unsigned long) chunksize_nomask (victim)
>= (unsigned long) (nb))
{
victim = victim->bk_nextsize;
while (((unsigned long) (size = chunksize (victim)) <
(unsigned long) (nb)))
victim = victim->bk_nextsize;
/* Avoid removing the first entry for a size so that the skip
list does not have to be rerouted. */
if (victim != last (bin)
&& chunksize_nomask (victim)
== chunksize_nomask (victim->fd))
victim = victim->fd;
remainder_size = size - nb;
unlink_chunk (av, victim);
/* Exhaust */
if (remainder_size < MINSIZE)
{
set_inuse_bit_at_offset (victim, size);
if (av != &main_arena)
set_non_main_arena (victim);
}
/* Split */
else
{
remainder = chunk_at_offset (victim, nb);
/* We cannot assume the unsorted list is empty and therefore
have to perform a complete insert here. */
bck = unsorted_chunks (av);
fwd = bck->fd;
if (__glibc_unlikely (fwd->bk != bck))
malloc_printerr ("malloc(): corrupted unsorted chunks");
last_re->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;
if (!in_smallbin_range (remainder_size))
{
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
set_foot (remainder, remainder_size);
}
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}
Se non viene trovato un chunk adatto per questo, continuare
Large Bin (successivo più grande)
Se nella large bin esatta non c'era alcun chunk che potesse essere utilizzato, iniziare a scorrere tutti i successivi large bin (a partire dal successivo più grande) fino a quando ne viene trovato uno (se presente).
Il resto del chunk diviso viene aggiunto nella unsorted bin, last_reminder viene aggiornato e viene eseguito lo stesso controllo di sicurezza:
bck->fd-> bk != bck: malloc(): chunk unsorted corrotti2
_int_malloc Large bin (successivo più grande)
```c // From https://github.com/bminor/glibc/blob/master/malloc/malloc.c#L4319C7-L4425C10
/* Search for a chunk by scanning bins, starting with next largest bin. This search is strictly by best-fit; i.e., the smallest (with ties going to approximately the least recently used) chunk that fits is selected.
The bitmap avoids needing to check that most blocks are nonempty. The particular case of skipping all bins during warm-up phases when no chunks have been returned yet is faster than it might look. */
++idx; bin = bin_at (av, idx); block = idx2block (idx); map = av->binmap[block]; bit = idx2bit (idx);
for (;; ) { /* Skip rest of block if there are no more set bits in this block. / if (bit > map || bit == 0) { do { if (++block >= BINMAPSIZE) / out of bins */ goto use_top; } while ((map = av->binmap[block]) == 0);
bin = bin_at (av, (block << BINMAPSHIFT)); bit = 1; }
/* Advance to bin with set bit. There must be one. */ while ((bit & map) == 0) { bin = next_bin (bin); bit <<= 1; assert (bit != 0); }
/* Inspect the bin. It is likely to be non-empty */ victim = last (bin);
/* If a false alarm (empty bin), clear the bit. / if (victim == bin) { av->binmap[block] = map &= ~bit; / Write through */ bin = next_bin (bin); bit <<= 1; }
else { size = chunksize (victim);
/* We know the first chunk in this bin is big enough to use. */ assert ((unsigned long) (size) >= (unsigned long) (nb));
remainder_size = size - nb;
/* unlink */ unlink_chunk (av, victim);
/* Exhaust */ if (remainder_size < MINSIZE) { set_inuse_bit_at_offset (victim, size); if (av != &main_arena) set_non_main_arena (victim); }
</details>
### Top Chunk
A questo punto, è il momento di ottenere un nuovo chunk dal Top chunk (se abbastanza grande).
Inizia con un controllo di sicurezza per assicurarsi che la dimensione del chunk non sia troppo grande (corrotta):
* `chunksize(av->top) > av->system_mem`: `malloc(): dimensione top corrotta`
Successivamente, verrà utilizzato lo spazio del top chunk se è abbastanza grande per creare un chunk della dimensione richiesta.\
Se non è abbastanza grande, se ci sono chunk veloci, consolidarli e riprovare.\
Infine, se non c'è abbastanza spazio, utilizzare `sysmalloc` per allocare la dimensione sufficiente.
<details>
<summary><code>_int_malloc</code> Top chunk</summary>
```c
use_top:
/*
If large enough, split off the chunk bordering the end of memory
(held in av->top). Note that this is in accord with the best-fit
search rule. In effect, av->top is treated as larger (and thus
less well fitting) than any other available chunk since it can
be extended to be as large as necessary (up to system
limitations).
We require that av->top always exists (i.e., has size >=
MINSIZE) after initialization, so if it would otherwise be
exhausted by current request, it is replenished. (The main
reason for ensuring it exists is that we may need MINSIZE space
to put in fenceposts in sysmalloc.)
*/
victim = av->top;
size = chunksize (victim);
if (__glibc_unlikely (size > av->system_mem))
malloc_printerr ("malloc(): corrupted top size");
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
{
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
av->top = remainder;
set_head (victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
set_head (remainder, remainder_size | PREV_INUSE);
check_malloced_chunk (av, victim, nb);
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
/* When we are using atomic ops to free fast chunks we can get
here for all block sizes. */
else if (atomic_load_relaxed (&av->have_fastchunks))
{
malloc_consolidate (av);
/* restore original bin index */
if (in_smallbin_range (nb))
idx = smallbin_index (nb);
else
idx = largebin_index (nb);
}
/*
Otherwise, relay to handle system-dependent cases
*/
else
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}
}
}
sysmalloc
Inizio di sysmalloc
Se l'arena è nulla o la dimensione richiesta è troppo grande (e sono consentiti mmaps rimasti), utilizzare sysmalloc_mmap per allocare spazio e restituirlo.
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2531/*sysmalloc handles malloc cases requiring more memory from the system.On entry, it is assumed that av->top does not have enoughspace to service request for nb bytes, thus requiring that av->topbe extended or replaced.*/staticvoid*sysmalloc (INTERNAL_SIZE_T nb, mstate av){mchunkptr old_top; /* incoming value of av->top */INTERNAL_SIZE_T old_size; /* its size */char*old_end; /* its end address */long size; /* arg to first MORECORE or mmap call */char*brk; /* return value from MORECORE */long correction; /* arg to 2nd MORECORE call */char*snd_brk; /* 2nd return val */INTERNAL_SIZE_T front_misalign; /* unusable bytes at front of new space */INTERNAL_SIZE_T end_misalign; /* partial page left at end of new space */char*aligned_brk; /* aligned offset into brk */mchunkptr p; /* the allocated/returned chunk */mchunkptr remainder; /* remainder from allocation */unsignedlong remainder_size; /* its size */size_t pagesize =GLRO (dl_pagesize);bool tried_mmap =false;/*If have mmap, and the request size meets the mmap threshold, andthe system supports mmap, and there are few enough currentlyallocated mmapped regions, try to directly map this requestrather than expanding top.*/if (av ==NULL|| ((unsignedlong) (nb) >= (unsignedlong) (mp_.mmap_threshold)&& (mp_.n_mmaps <mp_.n_mmaps_max))){char*mm;if (mp_.hp_pagesize >0&& nb >=mp_.hp_pagesize){/* There is no need to issue the THP madvise call if Huge Pages areused directly. */mm =sysmalloc_mmap (nb,mp_.hp_pagesize,mp_.hp_flags, av);if (mm != MAP_FAILED)return mm;}mm =sysmalloc_mmap (nb, pagesize,0, av);if (mm != MAP_FAILED)return mm;tried_mmap =true;}/* There are no usable arenas and mmap also failed. */if (av ==NULL)return0;
Controlli di sysmalloc
Inizia ottenendo le informazioni sul vecchio chunk superiore e verificando che alcune delle seguenti condizioni siano vere:
La dimensione del vecchio heap è 0 (nuovo heap)
La dimensione dell'heap precedente è maggiore di MINSIZE e il vecchio Top è in uso
L'heap è allineato alla dimensione della pagina (0x1000 quindi i 12 bit inferiori devono essere 0)
Poi controlla anche che:
La vecchia dimensione non abbia abbastanza spazio per creare un chunk della dimensione richiesta
/* Precondition: not enough current space to satisfy nb request */ assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));
</details>
### sysmalloc non arena principale
Prima cercherà di **estendere** l'heap precedente per questo heap. Se non è possibile, cercherà di **allocare un nuovo heap** e aggiornare i puntatori per poterlo utilizzare.\
Infine, se ciò non funziona, prova a chiamare **`sysmalloc_mmap`**. 
<details>
<summary>sysmalloc non arena principale</summary>
```c
if (av != &main_arena)
{
heap_info *old_heap, *heap;
size_t old_heap_size;
/* First try to extend the current heap. */
old_heap = heap_for_ptr (old_top);
old_heap_size = old_heap->size;
if ((long) (MINSIZE + nb - old_size) > 0
&& grow_heap (old_heap, MINSIZE + nb - old_size) == 0)
{
av->system_mem += old_heap->size - old_heap_size;
set_head (old_top, (((char *) old_heap + old_heap->size) - (char *) old_top)
| PREV_INUSE);
}
else if ((heap = new_heap (nb + (MINSIZE + sizeof (*heap)), mp_.top_pad)))
{
/* Use a newly allocated heap. */
heap->ar_ptr = av;
heap->prev = old_heap;
av->system_mem += heap->size;
/* Set up the new top. */
top (av) = chunk_at_offset (heap, sizeof (*heap));
set_head (top (av), (heap->size - sizeof (*heap)) | PREV_INUSE);
/* Setup fencepost and free the old top chunk with a multiple of
MALLOC_ALIGNMENT in size. */
/* The fencepost takes at least MINSIZE bytes, because it might
become the top chunk again later. Note that a footer is set
up, too, although the chunk is marked in use. */
old_size = (old_size - MINSIZE) & ~MALLOC_ALIGN_MASK;
set_head (chunk_at_offset (old_top, old_size + CHUNK_HDR_SZ),
0 | PREV_INUSE);
if (old_size >= MINSIZE)
{
set_head (chunk_at_offset (old_top, old_size),
CHUNK_HDR_SZ | PREV_INUSE);
set_foot (chunk_at_offset (old_top, old_size), CHUNK_HDR_SZ);
set_head (old_top, old_size | PREV_INUSE | NON_MAIN_ARENA);
_int_free (av, old_top, 1);
}
else
{
set_head (old_top, (old_size + CHUNK_HDR_SZ) | PREV_INUSE);
set_foot (old_top, (old_size + CHUNK_HDR_SZ));
}
}
else if (!tried_mmap)
{
/* We can at least try to use to mmap memory. If new_heap fails
it is unlikely that trying to allocate huge pages will
succeed. */
char *mm = sysmalloc_mmap (nb, pagesize, 0, av);
if (mm != MAP_FAILED)
return mm;
}
}
Arena principale di sysmalloc
Inizia calcolando la quantità di memoria necessaria. Inizierà richiedendo memoria contigua in modo da poter utilizzare la vecchia memoria non utilizzata. Vengono inoltre eseguite alcune operazioni di allineamento.
Arena principale di sysmalloc
```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2665C1-L2713C10
else /* av == main_arena */
{ /* Request enough space for nb + pad + overhead */ size = nb + mp_.top_pad + MINSIZE;
/* If contiguous, we can subtract out existing space that we hope to combine with new space. We add it back later only if we don't actually get contiguous space. */
if (contiguous (av)) size -= old_size;
/* Round to a multiple of page size or huge page size. If MORECORE is not contiguous, this ensures that we only call it with whole-page arguments. And if MORECORE is contiguous and this is not first time through, this preserves page-alignment of previous calls. Otherwise, we correct to page-align below. */
#ifdef MADV_HUGEPAGE /* Defined in brk.c. */ extern void *__curbrk; if (_glibc_unlikely (mp.thp_pagesize != 0)) { uintptr_t top = ALIGN_UP ((uintptr_t) _curbrk + size, mp.thp_pagesize); size = top - (uintptr_t) __curbrk; } else #endif size = ALIGN_UP (size, GLRO(dl_pagesize));
/* Don't try to call MORECORE if argument is so big as to appear negative. Note that since mmap takes size_t arg, it may succeed below even if we cannot call MORECORE. */
### Errore precedente dell'arena principale di sysmalloc 1
Se il precedente ha restituito `MORECORE_FAILURE`, prova di nuovo ad allocare memoria utilizzando `sysmalloc_mmap_fallback`
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L2715C7-L2740C10
if (brk == (char *) (MORECORE_FAILURE))
{
/*
If have mmap, try using it as a backup when MORECORE fails or
cannot be used. This is worth doing on systems that have "holes" in
address space, so sbrk cannot extend to give contiguous space, but
space is available elsewhere. Note that we ignore mmap max count
and threshold limits, since the space will not be used as a
segregated mmap region.
*/
char *mbrk = MAP_FAILED;
if (mp_.hp_pagesize > 0)
mbrk = sysmalloc_mmap_fallback (&size, nb, old_size,
mp_.hp_pagesize, mp_.hp_pagesize,
mp_.hp_flags, av);
if (mbrk == MAP_FAILED)
mbrk = sysmalloc_mmap_fallback (&size, nb, old_size, MMAP_AS_MORECORE_SIZE,
pagesize, 0, av);
if (mbrk != MAP_FAILED)
{
/* We do not need, and cannot use, another sbrk call to find end */
brk = mbrk;
snd_brk = brk + size;
}
}
sysmalloc continuazione dell'arena principale
Se il passaggio precedente non ha restituito MORECORE_FAILURE, se ha funzionato crea alcuni allineamenti:
