Bins & Memory Allocations

Zacznij od zera i stań się ekspertem od hakowania AWS dzięki htARTE (HackTricks AWS Red Team Expert)!

Inne sposoby wsparcia HackTricks:

Podstawowe Informacje

Aby poprawić efektywność przechowywania kawałków, każdy kawałek nie jest przechowywany tylko w jednym związku, ale istnieje kilka typów. Są to tzw. bins i istnieje 5 typów bins: 62 małych bins, 63 dużych bins, 1 bin niesortowany, 10 szybkich bins i 64 bins tcache na wątek.

Początkowy adres do każdego bin niesortowanego, małego i dużego znajduje się w tym samym tablicy. Indeks 0 jest nieużywany, 1 to bin niesortowany, biny 2-64 to małe biny, a biny 65-127 to duże biny.

Bins Tcache (Bufor na Wątek)

Mimo że wątki starają się mieć swoją własną stertę (patrz Areny i Podsterty), istnieje możliwość, że proces z wieloma wątkami (np. serwer internetowy) będzie dzielił stertę z innymi wątkami. W takim przypadku głównym rozwiązaniem jest użycie blokad, które mogą znacząco spowolnić wątki.

Dlatego tcache jest podobny do szybkiego bina na wątek w taki sposób, że jest to jednokierunkowa lista nie łącząca kawałków. Każdy wątek ma 64 jednokierunkowe biny tcache. Każdy bin może zawierać maksymalnie 7 kawałków o tej samej wielkości o rozmiarze 24 do 1032B na systemach 64-bitowych i 12 do 516B na systemach 32-bitowych.

Gdy wątek zwalnia kawałek, jeśli nie jest zbyt duży, aby być przydzielony do tcache, a odpowiedni bin tcache nie jest pełny (już 7 kawałków), zostanie tam przydzielony. Jeśli nie może trafić do tcache, będzie musiał poczekać na blokadę sterty, aby móc wykonać operację zwolnienia globalnie.

Gdy kawałek jest przydzielany, jeśli istnieje wolny kawałek wymaganego rozmiaru w Tcache, zostanie użyty, jeśli nie, będzie musiał poczekać na blokadę sterty, aby znaleźć go w globalnych binach lub utworzyć nowy. Istnieje także optymalizacja, w tym przypadku, podczas posiadania blokady sterty, wątek wypełni swoje Tcache kawałkami sterty (7) o żądanym rozmiarze, więc jeśli potrzebuje więcej, znajdzie je w Tcache.

Dodaj przykład kawałka tcache

```c #include #include

int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); free(chunk); return 0; }

Skompiluj go i debuguj z punktem przerwania w opcode ret z funkcji main. Następnie za pomocą gef możesz zobaczyć używany tcache bin:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=1] ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

Struktury i funkcje Tcache

W poniższym kodzie można zobaczyć maksymalne pojemniki i kawałki na indeks, strukturę tcache_entry stworzoną w celu uniknięcia podwójnych zwolnień oraz tcache_perthread_struct, strukturę, którą każdy wątek używa do przechowywania adresów do każdego indeksu pojemnika.

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

/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS		64
# define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)

/* Only used to pre-fill the tunables.  */
# define tidx2usize(idx)	(((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)

/* When "x" is from chunksize().  */
# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size.  */
# define usize2tidx(x) csize2tidx (request2size (x))

/* With rounding and alignment, the bins are...
idx 0   bytes 0..24 (64-bit) or 0..12 (32-bit)
idx 1   bytes 25..40 or 13..20
idx 2   bytes 41..56 or 21..28
etc.  */

/* This is another arbitrary limit, which tunables can change.  Each
tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 7

/* Maximum chunks in tcache bins for tunables.  This value must fit the range
of tcache->counts[] entries, else they may overflow.  */
# define MAX_TCACHE_COUNT UINT16_MAX

[...]

typedef struct tcache_entry
{
struct tcache_entry *next;
/* This field exists to detect double frees.  */
uintptr_t key;
} tcache_entry;

/* There is one of these for each thread, which contains the
per-thread cache (hence "tcache_perthread_struct").  Keeping
overall size low is mildly important.  Note that COUNTS and ENTRIES
are redundant (we could have just counted the linked list each
time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
uint16_t counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

Funkcja __tcache_init to funkcja, która tworzy i alokuje miejsce dla obiektu tcache_perthread_struct

kod tcache_init

```c // From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3241C1-L3274C2

static void tcache_init(void) { mstate ar_ptr; void *victim = 0; const size_t bytes = sizeof (tcache_perthread_struct);

if (tcache_shutting_down) return;

arena_get (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes); if (!victim && ar_ptr != NULL) { ar_ptr = arena_get_retry (ar_ptr, bytes); victim = _int_malloc (ar_ptr, bytes); }

if (ar_ptr != NULL) __libc_lock_unlock (ar_ptr->mutex);

/* In a low memory situation, we may not be able to allocate memory

  • in which case, we just keep trying later. However, we typically do this very early, so either there is sufficient memory, or there isn't enough memory to do non-trivial allocations anyway. */ if (victim) { tcache = (tcache_perthread_struct *) victim; memset (tcache, 0, sizeof (tcache_perthread_struct)); }

}

</details>

#### Indeksy Tcache

Tcache ma kilka kubełków w zależności od rozmiaru, a początkowe wskaźniki do **pierwszego fragmentu każdego indeksu oraz ilość fragmentów na indeks znajdują się wewnątrz fragmentu**. Oznacza to, że zlokalizowanie fragmentu z tą informacją (zazwyczaj pierwszego) pozwala znaleźć wszystkie początkowe punkty tcache i ilość fragmentów Tcache.

### Szybkie kubełki

Szybkie kubełki są zaprojektowane, aby **przyspieszyć alokację pamięci dla małych fragmentów**, trzymając niedawno zwolnione fragmenty w strukturze szybkiego dostępu. Te kubełki korzystają z podejścia Last-In, First-Out (LIFO), co oznacza, że **najbardziej niedawno zwolniony fragment jest pierwszy**, który zostanie ponownie użyty, gdy pojawi się nowe żądanie alokacji. To zachowanie jest korzystne dla szybkości, ponieważ szybciej jest wstawiać i usuwać z góry stosu (LIFO) w porównaniu do kolejki (FIFO).

Dodatkowo, **szybkie kubełki używają list jednokierunkowych**, a nie dwukierunkowych, co dodatkowo poprawia szybkość. Ponieważ fragmenty w szybkich kubełkach nie są łączone z sąsiadującymi, nie ma potrzeby skomplikowanej struktury, która pozwala na usuwanie z środka. Lista jednokierunkowa jest prostsza i szybsza dla tych operacji.

W zasadzie, to co się tutaj dzieje, to że nagłówek (wskaźnik do pierwszego fragmentu do sprawdzenia) zawsze wskazuje na najnowszy zwolniony fragment tego rozmiaru. Więc:

* Gdy alokowany jest nowy fragment tego rozmiaru, nagłówek wskazuje na wolny fragment do użycia. Ponieważ ten wolny fragment wskazuje na następny do użycia, ten adres jest przechowywany w nagłówku, aby następna alokacja wiedziała, gdzie znaleźć dostępny fragment.
* Gdy fragment jest zwalniany, wolny fragment zapisze adres bieżącego dostępnego fragmentu, a adres tego nowo zwolnionego fragmentu zostanie umieszczony w nagłówku.

Maksymalny rozmiar listy jednokierunkowej to `0x80`, a są one zorganizowane tak, że fragment o rozmiarze `0x20-0x2f` będzie w indeksie `0`, fragment o rozmiarze `0x30-0x3f` będzie w `idx` `1`...

<div data-gb-custom-block data-tag="hint" data-style='danger'>

Fragmenty w szybkich kubełkach nie są ustawione jako dostępne, więc są trzymane jako fragmenty szybkich kubełków przez pewien czas, zamiast móc łączyć się z innymi wolnymi fragmentami otaczającymi je.

</div>

```c
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Fastbins

An array of lists holding recently freed small chunks.  Fastbins
are not doubly linked.  It is faster to single-link them, and
since chunks are never removed from the middles of these lists,
double linking is not necessary. Also, unlike regular bins, they
are not even processed in FIFO order (they use faster LIFO) since
ordering doesn't much matter in the transient contexts in which
fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot
be consolidated with other free chunks. malloc_consolidate
releases all chunks in fastbins and consolidates them with
other free chunks.
*/

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

Duże pojemniki

W przeciwieństwie do małych pojemników, które zarządzają kawałkami o stałych rozmiarach, każdy duży pojemnik obsługuje zakres rozmiarów kawałków. Jest to bardziej elastyczne, pozwalając systemowi pomieścić różne rozmiary bez konieczności posiadania osobnego pojemnika dla każdego rozmiaru.

W alokatorze pamięci duże pojemniki zaczynają się tam, gdzie kończą się małe pojemniki. Zakresy dla dużych pojemników rosną stopniowo, co oznacza, że pierwszy pojemnik może obejmować kawałki od 512 do 576 bajtów, podczas gdy kolejny obejmuje 576 do 640 bajtów. Ten wzorzec się powtarza, a największy pojemnik zawiera wszystkie kawałki powyżej 1 MB.

Duże pojemniki są wolniejsze w obsłudze w porównaniu z małymi pojemnikami, ponieważ muszą sortować i przeszukiwać listę różnych rozmiarów kawałków, aby znaleźć najlepsze dopasowanie dla alokacji. Gdy kawałek jest wstawiany do dużego pojemnika, musi być posortowany, a podczas alokacji pamięci system musi znaleźć odpowiedni kawałek. Dodatkowa praca sprawia, że są one wolniejsze, ale ponieważ duże alokacje są mniej powszechne niż małe, jest to akceptowalny kompromis.

Istnieją:

  • 32 pojemniki o zakresie 64B (kolidują z małymi pojemnikami)

  • 16 pojemników o zakresie 512B (kolidują z małymi pojemnikami)

  • 8 pojemników o zakresie 4096B (częściowo kolidują z małymi pojemnikami)

  • 4 pojemniki o zakresie 32768B

  • 2 pojemniki o zakresie 262144B

  • 1 pojemnik na pozostałe rozmiary

Górny Kawałek

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Top

The top-most available chunk (i.e., the one bordering the end of
available memory) is treated specially. It is never included in
any bin, is used only if no other chunk is available, and is
released back to the system if it is very large (see
M_TRIM_THRESHOLD).  Because top initially
points to its own bin with initial zero size, thus forcing
extension on the first malloc request, we avoid having any special
code in malloc to check whether it even exists yet. But we still
need to do so when getting memory from system, so we make
initial_top treat the bin as a legal but unusable chunk during the
interval between initialization and the first call to
sysmalloc. (This is somewhat delicate, since it relies on
the 2 preceding words to be zero during this interval as well.)
*/

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

Podstawowo, to kawałek zawiera całą obecnie dostępną stertę. Gdy wykonywane jest malloc, jeśli nie ma dostępnego wolnego kawałka do użycia, ten kawałek wierzchołkowy będzie zmniejszał swoją wielkość, zapewniając niezbędną przestrzeń. Wskaźnik do kawałka wierzchołkowego jest przechowywany w strukturze malloc_state.

Co więcej, na początku możliwe jest użycie kawałka niesortowanego jako kawałka wierzchołkowego.

Ostatnie Przypomnienie

Kiedy używane jest malloc i kawałek jest podzielony (na przykład z listy niepołączonych lub z kawałka na szczycie), kawałek stworzony z reszty podzielonego kawałka nazywany jest Ostatnim Przypomnieniem, a jego wskaźnik jest przechowywany w strukturze malloc_state.

Przepływ Alokacji

Sprawdź:

Przepływ Zwolnienia

Sprawdź:

Sprawdzenia Bezpieczeństwa Funkcji Stosowanych w Stosie

Sprawdź sprawdzenia bezpieczeństwa wykonywane przez często używane funkcje w stosie w:

Odnośniki

Last updated