malloc & sysmalloc

Ucz się i ćwicz Hacking AWS:HackTricks Training AWS Red Team Expert (ARTE) Ucz się i ćwicz Hacking GCP: HackTricks Training GCP Red Team Expert (GRTE)

Wesprzyj HackTricks

• Sprawdź plany subskrypcyjne!

• Dołącz do 💬 grupy Discord lub grupy telegramowej lub śledź nas na Twitterze 🐦 @hacktricks_live.

• Dziel się trikami hakerskimi, przesyłając PR-y do HackTricks i HackTricks Cloud na githubie.

Podsumowanie kolejności alokacji

(W tym podsumowaniu nie są wyjaśnione żadne kontrole, a niektóre przypadki zostały pominięte dla zwięzłości)

1. __libc_malloc próbuje uzyskać kawałek z tcache, jeśli nie, wywołuje _int_malloc

2. _int_malloc :

3. Próbuje wygenerować arenę, jeśli jej nie ma

4. Jeśli istnieje jakiś kawałek fast bin odpowiedniego rozmiaru, użyj go

5. Wypełnij tcache innymi szybkimi kawałkami

6. Jeśli istnieje jakiś kawałek small bin odpowiedniego rozmiaru, użyj go

7. Wypełnij tcache innymi kawałkami tego samego rozmiaru

8. Jeśli żądany rozmiar nie jest dla małych binów, scal fast bin z unsorted bin

9. Sprawdź unsorted bin, użyj pierwszego kawałka z wystarczającą ilością miejsca

10. Jeśli znaleziony kawałek jest większy, podziel go, aby zwrócić część i dodaj resztę z powrotem do unsorted bin

11. Jeśli kawałek ma taki sam rozmiar jak żądany rozmiar, użyj go do wypełnienia tcache zamiast go zwracać (aż tcache będzie pełne, wówczas zwróć następny)

12. Dla każdego sprawdzonego kawałka mniejszego rozmiaru, umieść go w odpowiednim małym lub dużym binie

13. Sprawdź duży bin w indeksie żądanego rozmiaru

14. Zacznij od pierwszego kawałka, który jest większy niż żądany rozmiar, jeśli znajdziesz taki, zwróć go i dodaj resztki do małego bina

15. Sprawdź duże biny od następnych indeksów do końca

16. Od następnego większego indeksu sprawdź, czy jest jakiś kawałek, podziel pierwszy znaleziony kawałek, aby użyć go do żądanego rozmiaru i dodaj resztę do unsorted bin

17. Jeśli w poprzednich binach nic nie znaleziono, pobierz kawałek z top chunk

18. Jeśli top chunk nie był wystarczająco duży, powiększ go za pomocą sysmalloc

__libc_malloc

Funkcja malloc faktycznie wywołuje __libc_malloc. Ta funkcja sprawdzi tcache, aby zobaczyć, czy jest dostępny kawałek o pożądanym rozmiarze. Jeśli jest, użyje go, a jeśli nie, sprawdzi, czy jest to pojedynczy wątek, a w takim przypadku wywoła _int_malloc w głównej arenie, a jeśli nie, wywoła _int_malloc w arenie wątku.

Kod __libc_malloc

```c // From https://github.com/bminor/glibc/blob/master/malloc/malloc.c

#if IS_IN (libc) void * __libc_malloc (size_t bytes) { mstate ar_ptr; void *victim;

_Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2, "PTRDIFF_MAX is not more than half of SIZE_MAX");

if (!__malloc_initialized) ptmalloc_init (); #if USE_TCACHE /* int_free also calls request2size, be careful to not pad twice. */ size_t tbytes = checked_request2size (bytes); if (tbytes == 0) { __set_errno (ENOMEM); return NULL; } size_t tc_idx = csize2tidx (tbytes);

MAYBE_INIT_TCACHE ();

DIAG_PUSH_NEEDS_COMMENT; if (tc_idx < mp_.tcache_bins && tcache != NULL && tcache->counts[tc_idx] > 0) { victim = tcache_get (tc_idx); return tag_new_usable (victim); } DIAG_POP_NEEDS_COMMENT; #endif

if (SINGLE_THREAD_P) { victim = tag_new_usable (_int_malloc (&main_arena, bytes)); assert (!victim || chunk_is_mmapped (mem2chunk (victim)) || &main_arena == arena_for_chunk (mem2chunk (victim))); return victim; }

arena_get (ar_ptr, bytes);

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);

victim = tag_new_usable (victim);

assert (!victim || chunk_is_mmapped (mem2chunk (victim)) || ar_ptr == arena_for_chunk (mem2chunk (victim))); return victim; }

</details>

Zauważ, że zawsze oznacza zwrócony wskaźnik jako `tag_new_usable`, z kodu:
```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

To jest funkcja, która alokuje pamięć, korzystając z innych kubełków i najwyższego fragmentu.

• Start

Zaczyna od zdefiniowania kilku zmiennych i uzyskania rzeczywistego rozmiaru, jaki musi mieć przestrzeń pamięci żądania:

Fast Bin

Jeśli potrzebny rozmiar mieści się w rozmiarach Fast Bins, spróbuj użyć fragmentu z fast bin. W zasadzie, na podstawie rozmiaru znajdzie indeks fast bin, w którym powinny znajdować się poprawne fragmenty, i jeśli takie istnieją, zwróci jeden z nich. Ponadto, jeśli tcache jest włączone, wypełni tcache bin tego rozmiaru fragmentami z fast bins.

Podczas wykonywania tych działań, tutaj wykonywane są pewne kontrole bezpieczeństwa:

• Jeśli fragment jest źle wyrównany: malloc(): wykryto źle wyrównany fragment fastbin 2

• Jeśli następny fragment jest źle wyrównany: malloc(): wykryto źle wyrównany fragment fastbin

• Jeśli zwrócony fragment ma rozmiar, który nie jest poprawny ze względu na jego indeks w fast bin: malloc(): korupcja pamięci (fast)

• Jeśli którykolwiek fragment użyty do wypełnienia tcache jest źle wyrównany: malloc(): wykryto źle wyrównany fragment fastbin 3

```c /* If this is a large request, consolidate fastbins before continuing. While it might look excessive to kill all fastbins before even seeing if there is space available, this avoids fragmentation problems normally associated with fastbins. Also, in practice, programs tend to have runs of either small or large requests, but less often mixtures, so consolidation is not invoked all that often in most programs. And the programs that it is called frequently in otherwise tend to fragment. */

else { idx = largebin_index (nb); if (atomic_load_relaxed (&av->have_fastchunks)) malloc_consolidate (av); }

</details>

Funkcja konsolidacji malloca usuwa podstawowe bloki z szybkiego kubełka i umieszcza je w nieuporządkowanym kubełku. Po kolejnym mallocu te bloki zostaną zorganizowane w swoich odpowiednich małych/szybkich kubełkach.

Należy zauważyć, że podczas usuwania tych bloków, jeśli zostaną znalezione z poprzednimi lub następnymi blokami, które nie są używane, zostaną one **odłączone i scalone** przed umieszczeniem ostatecznego bloku w kubełku **nieuporządkowanym**.

Dla każdego bloku szybkiego kubełka wykonywane są kilka kontroli bezpieczeństwa:

* Jeśli blok jest niezgodny, wywołaj: `malloc_consolidate(): wykryto niezgodny blok szybkiego kubełka`
* Jeśli blok ma inną wielkość niż powinien z powodu indeksu, w którym się znajduje: `malloc_consolidate(): nieprawidłowa wielkość bloku`
* Jeśli poprzedni blok nie jest używany, a jego wielkość różni się od tej wskazanej przez `prev_chunk`: `uszkodzona wielkość vs. prev_size w fastbins`
```c
// https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L4810C1-L4905C2

static void malloc_consolidate(mstate av)
{
mfastbinptr*    fb;                 /* current fastbin being consolidated */
mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
mchunkptr       p;                  /* current chunk being consolidated */
mchunkptr       nextp;              /* next chunk to consolidate */
mchunkptr       unsorted_bin;       /* bin header */
mchunkptr       first_unsorted;     /* chunk to link to */

/* These have same use as in free() */
mchunkptr       nextchunk;
INTERNAL_SIZE_T size;
INTERNAL_SIZE_T nextsize;
INTERNAL_SIZE_T prevsize;
int             nextinuse;

atomic_store_relaxed (&av->have_fastchunks, false);

unsorted_bin = unsorted_chunks(av);

/*
Remove each chunk from fast bin and consolidate it, placing it
then in unsorted bin. Among other reasons for doing this,
placing in unsorted bin avoids needing to calculate actual bins
until malloc is sure that chunks aren't immediately going to be
reused anyway.
*/

maxfb = &fastbin (av, NFASTBINS - 1);
fb = &fastbin (av, 0);
do {
p = atomic_exchange_acquire (fb, NULL);
if (p != 0) {
do {
{
if (__glibc_unlikely (misaligned_chunk (p)))
malloc_printerr ("malloc_consolidate(): "
"unaligned fastbin chunk detected");

unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}

check_inuse_chunk(av, p);
nextp = REVEAL_PTR (p->fd);

/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
nextchunk = chunk_at_offset(p, size);
nextsize = chunksize(nextchunk);

if (!prev_inuse(p)) {
prevsize = prev_size (p);
size += prevsize;
p = chunk_at_offset(p, -((long) prevsize));
if (__glibc_unlikely (chunksize(p) != prevsize))
malloc_printerr ("corrupted size vs. prev_size in fastbins");
unlink_chunk (av, p);
}

if (nextchunk != av->top) {
nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

if (!nextinuse) {
size += nextsize;
unlink_chunk (av, nextchunk);
} else
clear_inuse_bit_at_offset(nextchunk, 0);

first_unsorted = unsorted_bin->fd;
unsorted_bin->fd = p;
first_unsorted->bk = p;

if (!in_smallbin_range (size)) {
p->fd_nextsize = NULL;
p->bk_nextsize = NULL;
}

set_head(p, size | PREV_INUSE);
p->bk = unsorted_bin;
p->fd = first_unsorted;
set_foot(p, size);
}

else {
size += nextsize;
set_head(p, size | PREV_INUSE);
av->top = p;
}

} while ( (p = nextp) != 0);

}
} while (fb++ != maxfb);
}

Nieposortowany blok

Nadszedł czas, aby sprawdzić nieposortowany blok w poszukiwaniu potencjalnego poprawnego fragmentu do użycia.

Rozpoczęcie

Zaczynamy od dużego pętli, która będzie przeszukiwać nieposortowany blok w kierunku bk aż do momentu dotarcia do końca (struktura areny) za pomocą while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))

Ponadto, po każdym rozważeniu nowego fragmentu wykonywane są pewne kontrole bezpieczeństwa:

• Jeśli rozmiar fragmentu jest dziwny (za mały lub za duży): malloc(): invalid size (unsorted)

• Jeśli rozmiar następnego fragmentu jest dziwny (za mały lub za duży): malloc(): invalid next size (unsorted)

• Jeśli rozmiar poprzedniego wskazanego przez następny fragment różni się od rozmiaru fragmentu: malloc(): mismatching next->prev_size (unsorted)

• Jeśli nie victim->bck->fd == victim lub nie victim->fd == av (arena): malloc(): unsorted double linked list corrupted

• Ponieważ zawsze sprawdzamy ostatni, jego fd powinien zawsze wskazywać na strukturę areny.

• Jeśli następny fragment nie wskazuje, że poprzedni jest w użyciu: malloc(): invalid next->prev_inuse (unsorted)

_int_malloc rozpoczęcie nieposortowanego bloku

```c /* Process recently freed or remaindered chunks, taking one only if it is exact fit, or, if this a small request, the chunk is remainder from the most recent non-exact fit. Place other traversed chunks in bins. Note that this step is the only place in any routine where chunks are placed in bins.

The outer loop here is needed because we might not realize until near the end of malloc that we should have consolidated, so must do so and retry. This happens at most once, and only when we would otherwise need to expand memory to service a "small" request. */

#if USE_TCACHE INTERNAL_SIZE_T tcache_nb = 0; size_t tc_idx = csize2tidx (nb); if (tcache != NULL && tc_idx < mp_.tcache_bins) tcache_nb = nb; int return_cached = 0;

tcache_unsorted_count = 0; #endif

for (;; ) { int iters = 0; while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av)) { bck = victim->bk; size = chunksize (victim); mchunkptr next = chunk_at_offset (victim, size);

if (__glibc_unlikely (size <= CHUNK_HDR_SZ) || __glibc_unlikely (size > av->system_mem)) malloc_printerr ("malloc(): invalid size (unsorted)"); if (__glibc_unlikely (chunksize_nomask (next) < CHUNK_HDR_SZ) || __glibc_unlikely (chunksize_nomask (next) > av->system_mem)) malloc_printerr ("malloc(): invalid next size (unsorted)"); if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size)) malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)"); if (__glibc_unlikely (bck->fd != victim) || __glibc_unlikely (victim->fd != unsorted_chunks (av))) malloc_printerr ("malloc(): unsorted double linked list corrupted"); if (__glibc_unlikely (prev_inuse (next))) malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

</details>

#### jeśli `in_smallbin_range`

Jeśli kawałek jest większy niż żądany rozmiar, użyj go i ustaw resztę przestrzeni kawałka na listę nieuporządkowaną oraz zaktualizuj `last_remainder` z nim.

<details>

<summary><code>_int_malloc</code> lista nieuporządkowana <code>in_smallbin_range</code></summary>
```c
// From https://github.com/bminor/glibc/blob/master/malloc/malloc.c#L4090C11-L4124C14

/*
If a small request, try to use last remainder if it is the
only chunk in unsorted bin.  This helps promote locality for
runs of consecutive small requests. This is the only
exception to best-fit, and applies only when there is
no exact fit for a small chunk.
*/

if (in_smallbin_range (nb) &&
bck == unsorted_chunks (av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
/* split and reattach remainder */
remainder_size = size - nb;
remainder = chunk_at_offset (victim, nb);
unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
av->last_remainder = remainder;
remainder->bk = remainder->fd = unsorted_chunks (av);
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;
}

Jeśli to się powiodło, zwróć fragment i koniec, jeśli nie, kontynuuj wykonywanie funkcji...

jeśli rozmiar jest równy

Kontynuuj usuwanie fragmentu z pojemnika, jeśli żądany rozmiar jest dokładnie taki sam jak rozmiar fragmentu:

• Jeśli pamięć podręczna (tcache) nie jest wypełniona, dodaj ją do pamięci podręcznej (tcache) i kontynuuj wskazując, że istnieje fragment pamięci podręcznej (tcache), który można wykorzystać

• Jeśli pamięć podręczna (tcache) jest pełna, po prostu jej użyj, zwracając ją

_int_malloc nieposortowany pojemnik o równym rozmiarze

```c // From https://github.com/bminor/glibc/blob/master/malloc/malloc.c#L4126C11-L4157C14

/* remove from unsorted list */ unsorted_chunks (av)->bk = bck; bck->fd = unsorted_chunks (av);

/* Take now instead of binning if exact fit */

if (size == nb) { set_inuse_bit_at_offset (victim, size); if (av != &main_arena) set_non_main_arena (victim); #if USE_TCACHE /* Fill cache first, return to user only if cache fills. We may return one of these chunks later. */ if (tcache_nb > 0 && tcache->counts[tc_idx] < mp_.tcache_count) { tcache_put (victim, tc_idx); return_cached = 1; continue; } else { #endif check_malloced_chunk (av, victim, nb); void *p = chunk2mem (victim); alloc_perturb (p, bytes); return p; #if USE_TCACHE } #endif }

</details>

Jeśli kawałek nie został zwrócony ani dodany do tcache, kontynuuj z kodem...

#### umieść kawałek w pojemniku

Przechowaj sprawdzony kawałek w małym pojemniku lub w dużym pojemniku zgodnie z rozmiarem kawałka (utrzymując odpowiednią organizację dużego pojemnika).

Wykonywane są kontrole bezpieczeństwa, aby upewnić się, że zarówno lista podwójnie połączona dużego pojemnika, jak i lista podwójnie połączona dużego pojemnika nie są uszkodzone:

* Jeśli `fwd->bk_nextsize->fd_nextsize != fwd`: `malloc(): lista podwójnie połączona dużego pojemnika jest uszkodzona (nextsize)`
* Jeśli `fwd->bk->fd != fwd`: `malloc(): lista podwójnie połączona dużego pojemnika jest uszkodzona (bk)`

<details>

<summary><code>_int_malloc</code> umieść kawałek w pojemniku</summary>
```c
/* place chunk in bin */

if (in_smallbin_range (size))
{
victim_index = smallbin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;
}
else
{
victim_index = largebin_index (size);
bck = bin_at (av, victim_index);
fwd = bck->fd;

/* maintain large bins in sorted order */
if (fwd != bck)
{
/* Or with inuse bit to speed comparisons */
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
assert (chunk_main_arena (bck->bk));
if ((unsigned long) (size)
< (unsigned long) chunksize_nomask (bck->bk))
{
fwd = bck;
bck = bck->bk;

victim->fd_nextsize = fwd->fd;
victim->bk_nextsize = fwd->fd->bk_nextsize;
fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
}
else
{
assert (chunk_main_arena (fwd));
while ((unsigned long) size < chunksize_nomask (fwd))
{
fwd = fwd->fd_nextsize;
assert (chunk_main_arena (fwd));
}

if ((unsigned long) size
== (unsigned long) chunksize_nomask (fwd))
/* Always insert in the second position.  */
fwd = fwd->fd;
else
{
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
if (bck->fd != fwd)
malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
}
}
else
victim->fd_nextsize = victim->bk_nextsize = victim;
}

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

Limity funkcji _int_malloc

W tym momencie, jeśli jakiś fragment został przechowywany w tcache i może zostać użyty, a limit został osiągnięty, po prostu zwróć fragment tcache.

Co więcej, jeśli osiągnięto MAX_ITERS, przerwij pętlę i pobierz fragment w inny sposób (górny fragment).

Jeśli ustawiono return_cached, po prostu zwróć fragment z tcache, aby uniknąć większych wyszukiwań.

// 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

Jeśli limity nie zostały osiągnięte, kontynuuj z kodem...

Duży kubełek (według indeksu)

Jeśli żądanie jest duże (nie znajduje się w małym kubełku) i nie zwróciliśmy jeszcze żadnego fragmentu, pobierz indeks żądanej wielkości w dużym kubełku, sprawdź, czy nie jest pusty lub czy największy fragment w tym kubełku jest większy niż żądana wielkość, a w takim przypadku znajdź najmniejszy fragment, który można wykorzystać dla żądanej wielkości.

Jeśli pozostała przestrzeń z ostatecznie użytego fragmentu może być nowym fragmentem, dodaj go do kubełka nieuporządkowanego, a ostatnia_pamięć jest aktualizowana.

Wykonywana jest kontrola bezpieczeństwa podczas dodawania przypomnienia do kubełka nieuporządkowanego:

• bck->fd-> bk != bck: malloc(): uszkodzone nieuporządkowane fragmenty

_int_malloc Duży kubełek (według indeksu)

```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; } }

</details>

Jeśli kawałek nie zostanie znaleziony odpowiedni, kontynuuj

### Duży kubełek (następnie większy)

Jeśli w dokładnym dużym kubełku nie ma żadnego kawałka, który mógłby być użyty, zacznij iterować przez wszystkie kolejne duże kubełki (zaczynając od natychmiast większego), aż zostanie znaleziony (jeśli taki istnieje).

Reszta podzielonego kawałka jest dodawana do kubełka nieuporządkowanego, ostatnia reszta jest aktualizowana, a wykonywana jest ta sama kontrola bezpieczeństwa:

* `bck->fd-> bk != bck`: `malloc(): corrupted unsorted chunks2`

<details>

<summary><code>_int_malloc</code> Duży kubełek (następnie większy)</summary>
```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);
}

/* 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 2");
remainder->bk = bck;
remainder->fd = fwd;
bck->fd = remainder;
fwd->bk = remainder;

/* advertise as last remainder */
if (in_smallbin_range (nb))
av->last_remainder = 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;
}
}

Górny kawałek

W tym momencie nadszedł czas, aby uzyskać nowy kawałek z Górnego kawałka (jeśli jest wystarczająco duży).

Zaczyna się od sprawdzenia bezpieczeństwa, upewniając się, że rozmiar kawałka nie jest zbyt duży (uszkodzony):

• chunksize(av->top) > av->system_mem: malloc(): uszkodzony rozmiar górnego kawałka

Następnie zostanie użyte miejsce z górnego kawałka, jeśli jest wystarczająco duże, aby utworzyć kawałek o żądanym rozmiarze. Jeśli nie ma wystarczająco dużo miejsca, a istnieją szybkie kawałki, zostaną one scalone, a następnie spróbowane ponownie. W końcu, jeśli nie ma wystarczająco dużo miejsca, użyj sysmalloc, aby zaalokować odpowiedni rozmiar.

_int_malloc Górny kawałek

```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

### rozpoczęcie sysmalloc

Jeśli arena jest pusta lub żądany rozmiar jest zbyt duży (i pozostały dozwolone mmaps), użyj `sysmalloc_mmap` do zaalokowania przestrzeni i zwróć ją.
```c
// 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 enough
space to service request for nb bytes, thus requiring that av->top
be extended or replaced.
*/

static void *
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 */
unsigned long 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, and
the system supports mmap, and there are few enough currently
allocated mmapped regions, try to directly map this request
rather than expanding top.
*/

if (av == NULL
|| ((unsigned long) (nb) >= (unsigned long) (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 are
used 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)
return 0;

Sprawdzanie sysmalloc

Zaczyna od uzyskania informacji o starym szczycie bloku i sprawdzenia, czy niektóre z następujących warunków są spełnione:

• Stary rozmiar sterty wynosi 0 (nowa sterta)

• Rozmiar poprzedniej sterty jest większy niż MINSIZE, a stary Top jest w użyciu

• Sterta jest wyrównana do rozmiaru strony (0x1000, więc dolne 12 bitów muszą być równe 0)

Następnie sprawdza również, czy:

• Stary rozmiar nie ma wystarczająco miejsca, aby utworzyć kawałek o żądanym rozmiarze

Sprawdzanie sysmalloc

```c /* Record incoming configuration of top */

old_top = av->top; old_size = chunksize (old_top); old_end = (char *) (chunk_at_offset (old_top, old_size));

brk = snd_brk = (char *) (MORECORE_FAILURE);

/* If not the first time through, we require old_size to be at least MINSIZE and to have prev_inuse set. */

assert ((old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0));

/* Precondition: not enough current space to satisfy nb request */ assert ((unsigned long) (old_size) < (unsigned long) (nb + MINSIZE));

### sysmalloc nie główna arena

Najpierw spróbuje **rozszerzyć** poprzedni stert dla tego sterty. Jeśli to nie jest możliwe, spróbuj **przydzielić nową stertę** i zaktualizuj wskaźniki, aby móc jej użyć.\
W końcu, jeśli to nie zadziała, spróbuj wywołać **`sysmalloc_mmap`**. 

</details>
```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;
}
}

Główna arena sysmalloc

Zaczyna obliczać potrzebną ilość pamięci. Rozpocznie od żądania ciągłej pamięci, dzięki czemu będzie można wykorzystać starą pamięć niewykorzystaną. Wykonywane są również pewne operacje wyrównania.

// 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.
*/

if (size > 0)
{
brk = (char *) (MORECORE (size));
if (brk != (char *) (MORECORE_FAILURE))
madvise_thp (brk, size);
LIBC_PROBE (memory_sbrk_more, 2, brk, size);
}

sysmalloc główna arena poprzedni błąd 1

Jeśli poprzednio zwrócono MORECORE_FAILURE, spróbuj ponownie przydzielić pamięć, używając sysmalloc_mmap_fallback

// 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;
}
}

Kontynuacja głównej areny sysmalloc

Jeśli poprzednia operacja nie zwróciła MORECORE_FAILURE, jeśli zadziałała, utwórz pewne wyrównania: