malloc & sysmalloc

Jifunze na zoezi la AWS Hacking:Mafunzo ya HackTricks AWS Red Team Expert (ARTE) Jifunze na zoezi la GCP Hacking: Mafunzo ya HackTricks GCP Red Team Expert (GRTE)

Support HackTricks

• Angalia mpango wa usajili!

• Jiunge na 💬 Kikundi cha Discord au kikundi cha telegram au tufuate kwenye Twitter 🐦 @hacktricks_live.

• Shiriki mbinu za udukuzi kwa kuwasilisha PRs kwa HackTricks na HackTricks Cloud repos za github.

Muhtasari wa Mpangilio wa Kutengwa

(Hakuna ukaguzi ulioelezwa katika muhtasari huu na baadhi ya kesi zimeachwa kwa kifupi)

1. __libc_malloc inajaribu kupata kipande kutoka kwa tcache, ikiwa hakuna, inaita _int_malloc

2. _int_malloc :

3. Inajaribu kuzalisha uwanja ikiwa haupo

4. Ikiwa kuna kipande cha bakuli la haraka la saizi sahihi, litumie

5. Jaza tcache na vipande vingine vya haraka

6. Ikiwa kuna kipande cha bakuli dogo la saizi sahihi, litumie

7. Jaza tcache na vipande vingine vya saizi hiyo

8. Ikiwa saizi inayohitajika sio kwa bakuli ndogo, unganisha bakuli la haraka na bakuli lisilo na mpangilio

9. Angalia bakuli lisilo na mpangilio, tumia kipande cha kwanza chenye nafasi ya kutosha

10. Ikiwa kipande kilichopatikana ni kikubwa, kigawe ili kurudisha sehemu na kuongeza kumbukumbu iliyobaki kwenye bakuli lisilo na mpangilio

11. Ikiwa kipande ni saizi sawa na ile inayohitajika, tumia kujaza tcache badala ya kurudisha (hadi tcache itakapojaa, kisha rudisha kipande kifuatacho)

12. Kwa kila kipande cha saizi ndogo kilichochunguzwa, weka kwenye bakuli lake dogo au kubwa husika

13. Angalia bakuli kubwa katika kiashiria cha saizi inayohitajika

14. Anza kutazama kutoka kwa kipande cha kwanza kilichobwa kuliko saizi inayohitajika, ikiwa kuna, rudisha na ongeza kumbukumbu kwa bakuli dogo

15. Angalia bakuli kubwa kutoka viashiria vya pili hadi mwisho

16. Kutoka kwa kiashiria kikubwa kinachofuata, angalia kipande chochote, gawa kipande cha kwanza kilichopatikana kutumia kwa saizi inayohitajika na ongeza kumbukumbu kwa bakuli lisilo na mpangilio

17. Ikiwa hakuna kitu kilichopatikana katika bakuli za awali, pata kipande kutoka kwa kipande cha juu

18. Ikiwa kipande cha juu hakikuwa kikubwa vya kutosha, engeza na sysmalloc

__libc_malloc

Kazi ya malloc kimsingi inaita __libc_malloc. Kazi hii itachunguza tcache kuona ikiwa kuna kipande kinachopatikana cha saizi inayotakiwa. Ikiwa kipo, itakitumia na ikiwa hakipo, itachunguza ikiwa ni mnyororo mmoja wa wateja na katika kesi hiyo itaita _int_malloc katika uwanja mkuu, na ikiwa sivyo, itaita _int_malloc katika uwanja wa mnyororo.

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

Tazama jinsi itakavyoweka lebo kwenye pointer iliyorejeshwa daima na tag_new_usable, kutoka kwenye msimbo:

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

Hii ni function inayoweza kugawa kumbukumbu kwa kutumia bins nyingine na kipande cha juu.

• Kuanza

Inaanza kwa kufafanua baadhi ya vars na kupata ukubwa halisi ambao nafasi ya kumbukumbu ya ombi inahitaji kuwa nayo:

_int_malloc start

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3847 static void * _int_malloc (mstate av, size_t bytes) { INTERNAL_SIZE_T nb; /* normalized request size */ unsigned int idx; /* associated bin index */ mbinptr bin; /* associated bin */

mchunkptr victim; /* inspected/selected chunk / INTERNAL_SIZE_T size; / its size / int victim_index; / its bin index */

mchunkptr remainder; /* remainder from a split / unsigned long remainder_size; / its size */

unsigned int block; /* bit map traverser / unsigned int bit; / bit map traverser / unsigned int map; / current word of binmap */

mchunkptr fwd; /* misc temp for linking / mchunkptr bck; / misc temp for linking */

#if USE_TCACHE size_t tcache_unsorted_count; /* count of unsorted chunks processed */ #endif

/* Convert request size to internal form by adding SIZE_SZ bytes overhead plus possibly more to obtain necessary alignment and/or to obtain a size of at least MINSIZE, the smallest allocatable size. Also, checked_request2size returns false for request sizes that are so large that they wrap around zero when padded and aligned. */

nb = checked_request2size (bytes); if (nb == 0) { __set_errno (ENOMEM); return NULL; }

</details>

### Uwanja

Katika tukio lisilowezekana kwamba hakuna uwanja wa kutumika, inatumia `sysmalloc` kupata kipande kutoka `mmap`:

<details>

<summary>_int_malloc si uwanja</summary>
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3885C3-L3893C6
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
mmap.  */
if (__glibc_unlikely (av == NULL))
{
void *p = sysmalloc (nb, av);
if (p != NULL)
alloc_perturb (p, bytes);
return p;
}

Fast Bin

Ikiwa ukubwa unaohitajika uko ndani ya ukubwa wa Fast Bins, jaribu kutumia kipande kutoka kwa fast bin. Kimsingi, kulingana na ukubwa, itapata index ya fast bin ambapo vipande halali vinapaswa kuwa vipo, na ikiwa kipo, itarudisha moja kati ya hizo. Zaidi ya hayo, ikiwa tcache imewezeshwa, itajaza tcache bin ya ukubwa huo na fast bins.

Wakati wa kutekeleza hatua hizi, ukaguzi wa usalama fulani hufanywa hapa:

• Ikiwa kipande hakijalingana: malloc(): kipande cha fastbin kilichojilinganisha 2

• Ikiwa kipande cha mbele hakilingani: malloc(): kipande cha fastbin kilichojilinganisha

• Ikiwa kipande kilichorudishwa kina ukubwa usio sahihi kwa sababu ya index yake kwenye fast bin: malloc(): ufisadi wa kumbukumbu (haraka)

• Ikiwa kipande chochote kilichotumika kujaza tcache hakilingani: malloc(): kipande cha fastbin kilichojilinganisha 3

_int_malloc fast bin

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3895C3-L3967C6 /* If the size qualifies as a fastbin, first check corresponding bin. This code is safe to execute even if av is not yet initialized, so we can try it without checking, which saves some time on this fast path. */

#define REMOVE_FB(fb, victim, pp) do { victim = pp; if (victim == NULL) break; pp = REVEAL_PTR (victim->fd); if (__glibc_unlikely (pp != NULL && misaligned_chunk (pp))) malloc_printerr ("malloc(): unaligned fastbin chunk detected"); } while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) != victim); \

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ())) { idx = fastbin_index (nb); mfastbinptr *fb = &fastbin (av, idx); mchunkptr pp; victim = *fb;

if (victim != NULL) { if (__glibc_unlikely (misaligned_chunk (victim))) malloc_printerr ("malloc(): unaligned fastbin chunk detected 2");

if (SINGLE_THREAD_P) fb = REVEAL_PTR (victim->fd); else REMOVE_FB (fb, pp, victim); if (__glibc_likely (victim != NULL)) { size_t victim_idx = fastbin_index (chunksize (victim)); if (__builtin_expect (victim_idx != idx, 0)) malloc_printerr ("malloc(): memory corruption (fast)"); check_remalloced_chunk (av, victim, nb); #if USE_TCACHE / While we're here, if we see other chunks of the same size, stash them in the tcache. */ size_t tc_idx = csize2tidx (nb); if (tcache != NULL && tc_idx < mp_.tcache_bins) { mchunkptr tc_victim;

/* While bin not empty and tcache not full, copy chunks. */ while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = *fb) != NULL) { if (__glibc_unlikely (misaligned_chunk (tc_victim))) malloc_printerr ("malloc(): unaligned fastbin chunk detected 3"); if (SINGLE_THREAD_P) *fb = REVEAL_PTR (tc_victim->fd); else { REMOVE_FB (fb, pp, tc_victim); if (__glibc_unlikely (tc_victim == NULL)) break; } tcache_put (tc_victim, tc_idx); } } #endif void *p = chunk2mem (victim); alloc_perturb (p, bytes); return p; } } }

</details>

### Bin ndogo

Kama ilivyoelezwa katika maoni, small bins hushikilia saizi moja kwa kila index, hivyo kuangalia ikiwa kipande halali kipo ni haraka sana, kwa hivyo baada ya fast bins, small bins huchunguzwa.

Uchunguzi wa kwanza ni kujua ikiwa saizi iliyohitajika inaweza kuwa ndani ya small bin. Katika kesi hiyo, pata **index** inayolingana ndani ya small bin na uone ikiwa kuna **kipande kinachopatikana**.

Kisha, ukaguzi wa usalama hufanywa ukiangalia:

- ikiwa `victim->bk->fd = victim`. Ili kuona kwamba vipande vyote vimeunganishwa kwa usahihi.

Katika kesi hiyo, kipande **kinapata biti ya `inuse`,** orodha iliyolingana imefanyiwa marekebisho ili kipande hiki kiondoke kutoka kwake (kwani kitatumika), na biti ya uga wa sio uwanja mkuu inawekwa ikiwa inahitajika.

Hatimaye, **jaza index ya tcache ya saizi iliyohitajika** na vipande vingine ndani ya small bin (ikiwa ipo).

<details>

<summary>_int_malloc small bin</summary>
```c
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3895C3-L3967C6

/*
If a small request, check regular bin.  Since these "smallbins"
hold one size each, no searching within bins is necessary.
(For a large request, we need to wait until unsorted chunks are
processed to find best fit. But for small ones, fits are exact
anyway, so we can check now, which is faster.)
*/

if (in_smallbin_range (nb))
{
idx = smallbin_index (nb);
bin = bin_at (av, idx);

if ((victim = last (bin)) != bin)
{
bck = victim->bk;
if (__glibc_unlikely (bck->fd != victim))
malloc_printerr ("malloc(): smallbin double linked list corrupted");
set_inuse_bit_at_offset (victim, nb);
bin->bk = bck;
bck->fd = bin;

if (av != &main_arena)
set_non_main_arena (victim);
check_malloced_chunk (av, victim, nb);
#if USE_TCACHE
/* While we're here, if we see other chunks of the same size,
stash them in the tcache.  */
size_t tc_idx = csize2tidx (nb);
if (tcache != NULL && tc_idx < mp_.tcache_bins)
{
mchunkptr tc_victim;

/* While bin not empty and tcache not full, copy chunks over.  */
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = last (bin)) != bin)
{
if (tc_victim != 0)
{
bck = tc_victim->bk;
set_inuse_bit_at_offset (tc_victim, nb);
if (av != &main_arena)
set_non_main_arena (tc_victim);
bin->bk = bck;
bck->fd = bin;

tcache_put (tc_victim, tc_idx);
}
}
}
#endif
void *p = chunk2mem (victim);
alloc_perturb (p, bytes);
return p;
}
}

malloc_consolidate

Ikiwa sio kipande kidogo, ni kipande kikubwa, na katika kesi hii malloc_consolidate huitwa kuepuka ufaaji wa kumbukumbu.

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

Kazi ya kufunga malloc kimsingi inaondoa vipande kutoka kwa bakuli la haraka na kuvitia kwenye bakuli lisilo na mpangilio. Baada ya malloc inayofuata vipande hivi vitapangwa katika bakuli zao ndogo/haraka husika.

Tafadhali kumbuka kwamba wakati wa kuondoa vipande hivi, ikiwa vitapatikana na vipande vilivyopita au vifuatavyo ambavyo havitumiwi vitakuwa havijapendwa na kufungwa kabla ya kuweka kipande cha mwisho kwenye bakuli lisilo na mpangilio.

Kwa kila kipande cha bakuli la haraka, ukaguzi wa usalama unafanywa:

• Ikiwa kipande hakiko sawa, kuzindua: malloc_consolidate(): kipande cha haraka kisichofungamana kiligunduliwa

• Ikiwa kipande kina ukubwa tofauti na ile inayopaswa kwa sababu ya kiashiria kilichomo: malloc_consolidate(): ukubwa batili wa kipande

• Ikiwa kipande kilichopita hakitumiwi na kipande kilichopita kina ukubwa tofauti na ule ulioonyeshwa na kipande_kilichopita: ukubwa ulioharibika dhidi ya ukubwa wa awali katika fastbins

Kazi ya kufunga malloc

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

</details>

### Bakuli lisilojumuishwa

Ni wakati wa kuangalia bakuli lisilojumuishwa kwa kipande halali kinachoweza kutumika.

#### Kuanza

Hii inaanza na kwa kwa kubwa ambayo itakuwa ikipitia bakuli lisilojumuishwa kwa mwelekeo wa `bk` hadi itakapofika mwisho (muundo wa uwanja) na `while ((mwathirika = vipande vilivyochanganyika (av)->bk) != vipande vilivyochanganyika (av))`&#x20;

Zaidi ya hayo, ukaguzi wa usalama hufanywa kila wakati kipande kipya kinachukuliwa:

* Ikiwa ukubwa wa kipande ni wa ajabu (mdogo sana au mkubwa sana): `malloc(): ukubwa usiofaa (lisilojumuishwa)`
* Ikiwa ukubwa wa kipande kinachofuata ni wa ajabu (mdogo sana au mkubwa sana): `malloc(): ukubwa usiofaa ufuatao (lisilojumuishwa)`
* Ikiwa ukubwa uliotangazwa na kipande kinachofuata unatofautiana na ukubwa wa kipande: `malloc(): kutofautiana next->prev_size (lisilojumuishwa)`
* Ikiwa si `mwathirika->bck->fd == mwathirika` au si `mwathirika->fd == av` (uwanja): `malloc(): orodha iliyoharibiwa ya viungo vya mara mbili (lisilojumuishwa)`
* Kwa kuwa tunakagua daima ya mwisho, `fd` yake inapaswa kuwa ikielekeza daima kwa muundo wa uwanja.
* Ikiwa kipande kinachofuata hakionyeshi kuwa kipande kilichopita kina matumizi: `malloc(): next->prev_inuse batili (lisilojumuishwa)`

<details>

<summary><code>_int_malloc</code> kuanza kwa bakuli lisilojumuishwa</summary>
```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)");

ikiwa in_smallbin_range

Ikiwa kipande ni kikubwa kuliko ukubwa ulioombwa litumike, na weka sehemu iliyobaki ya kipande kwenye orodha isiyopangwa na sasisha last_remainder nayo.

_int_malloc orodha isiyopangwa in_smallbin_range

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

</details>

Ikiwa hii ilikuwa mafanikio, rudisha kipande na hiyo ndiyo mwisho, failure kama sivyo, endelea kutekeleza kazi...

#### ikiwa saizi ni sawa

Endelea kuondoa kipande kutoka kwenye bin, kama saizi iliyohitajika ni sawa na ile ya kipande:

* Ikiwa tcache haijajazwa, weka kipande hicho kwenye tcache na endelea kuonyesha kuwa kuna kipande cha tcache kinachoweza kutumika
* Ikiwa tcache imejaa, litumie tu kwa kurudisha
```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
}

Ikiwa kipande hakijarudishwa au kuongezwa kwenye tcache, endelea na kanuni...

weka kipande kwenye bakuli

Hifadhi kipande kilichochunguzwa kwenye bakuli dogo au kwenye bakuli kubwa kulingana na ukubwa wa kipande (ukiweka bakuli kubwa vizuri).

Kuna ukaguzi wa usalama unaoendelea kuhakikisha kuwa orodha iliyofungwa maradufu ya bakuli kubwa imeharibiwa:

• Ikiwa fwd->bk_nextsize->fd_nextsize != fwd: malloc(): orodha iliyofungwa maradufu ya bakuli kubwa imeharibiwa (nextsize)

• Ikiwa fwd->bk->fd != fwd: malloc(): orodha iliyofungwa maradufu ya bakuli kubwa imeharibiwa (bk)

_int_malloc weka kipande kwenye bakuli

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

#### Vipimo vya `_int_malloc`

Kufikia hatua hii, ikiwa kipande fulani kilihifadhiwa kwenye tcache ambacho kinaweza kutumika na kikomo kimefikiwa, basi **rudisha kipande cha tcache**.

Zaidi ya hayo, ikiwa **MAX\_ITERS** imefikiwa, vunja kutoka kwenye mzunguko na pata kipande kwa njia tofauti (kipande cha juu).

Ikiwa `return_cached` imewekwa, rudisha kipande kutoka kwenye tcache ili kuepuka utafutaji mkubwa zaidi.
```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

Ikiwa vikwazo havijafikiwa, endelea na nambari...

Bin Kubwa (kwa index)

Ikiwa ombi ni kubwa (siyo kwenye bin ndogo) na bado hatujarudisha kipande chochote, pata index ya ukubwa ulioombwa kwenye bin kubwa, angalia kama si tupu au kama kipande kikubwa zaidi katika huu bin ni kikubwa zaidi kuliko ukubwa ulioombwa na katika kesi hiyo pata kipande kidogo zaidi kinachoweza kutumika kwa ukubwa ulioombwa.

Ikiwa nafasi iliyobaki kutoka kwenye kipande kilichotumika mwishowe inaweza kuwa kipande kipya, ongeza kwenye bin isiyopangwa na lsast_reminder inasasishwa.

Uchunguzi wa usalama unafanywa wakati wa kuongeza kipande kipya kwenye bin isiyopangwa:

• bck->fd-> bk != bck: malloc(): corrupted unsorted chunks

_int_malloc Bin Kubwa (kwa index)

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

Ikiwa kipande hakipatikani kufaa kwa hili, endelea

### Bakuli Kubwa (kikubwa kifuatacho)

Ikiwa hakukuwa na kipande chochote kinachoweza kutumika kwenye bakuli kubwa la moja kwa moja, anza kutafuta kupitia bakuli kubwa zote zifuatazo (kuanzia kwa kubwa mara moja) hadi kimoja kinapatikana (ikiwapo kipo).

Kukumbusha cha kipande kilichogawanywa huongezwa kwenye bakuli lisilo na mpangilio, `last_reminder` inasasishwa na ukaguzi sawa wa usalama unafanywa:

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

<details>

<summary><code>_int_malloc</code> Bakuli Kubwa (kikubwa kifuatacho)</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;