Heap

Podstawy sterty

Sterta to miejsce, w którym program będzie mógł przechowywać dane, gdy żąda ich, wywołując funkcje takie jak malloc, calloc... Ponadto, gdy pamięć ta nie jest już potrzebna, zostaje ona udostępniona poprzez wywołanie funkcji free.

Jak pokazano, znajduje się tuż po załadowaniu binarnego pliku do pamięci (sprawdź sekcję [heap]):

Podstawowe przydziały bloków

Gdy żądane jest przechowywanie danych na stercie, alokowana jest dla nich przestrzeń na stercie. Ta przestrzeń będzie należeć do bloku, a zarezerwowane zostaną tylko dane żądane + przestrzeń nagłówków bloku + minimalne przesunięcie rozmiaru bloku. Celem jest zarezerwowanie jak najmniejszej ilości pamięci, aby nie komplikować odnajdywania każdego bloku. W tym celu używane są informacje o metadanych bloku, aby wiedzieć, gdzie znajduje się każdy używany/wolny blok.

Istnieją różne sposoby rezerwacji przestrzeni głównie w zależności od używanego bloku, ale ogólna metodologia wygląda następująco:

Program zaczyna od żądania określonej ilości pamięci.
Jeśli na liście bloków jest ktoś dostępny, kto jest wystarczająco duży, aby zaspokoić żądanie, zostanie użyty.
Może to nawet oznaczać, że część dostępnego bloku zostanie użyta do tego żądania, a reszta zostanie dodana do listy bloków.
Jeśli na liście nie ma dostępnego bloku, ale wciąż jest miejsce w przydzielonej pamięci sterty, menedżer sterty tworzy nowy blok.
Jeśli nie ma wystarczająco dużo miejsca na stercie, aby przydzielić nowy blok, menedżer sterty prosi jądro o rozszerzenie pamięci przydzielonej dla sterty, a następnie używa tej pamięci do wygenerowania nowego bloku.
Jeśli wszystko zawiedzie, malloc zwraca wartość null.

Zauważ, że jeśli żądana pamięć przekroczy pewny próg, zostanie użyte mmap do zmapowania żądanej pamięci.

Areny

W aplikacjach wielowątkowych, menedżer sterty musi zapobiegać warunkom wyścigowym, które mogą prowadzić do awarii. Początkowo było to realizowane za pomocą globalnego mutexa, aby zapewnić, że tylko jeden wątek mógł mieć dostęp do sterty w danym momencie, ale spowodowało to problemy wydajnościowe z powodu wąskiego gardła spowodowanego mutexem.

Aby temu zaradzić, alokator sterty ptmalloc2 wprowadził "areny", gdzie każda arena działa jako oddzielna sterta z własnymi strukturami danych i mutexem, pozwalając wielu wątkom wykonywać operacje na stercie bez ingerencji w siebie nawzajem, o ile korzystają z różnych aren.

Domyślna "główna" arena obsługuje operacje sterty dla aplikacji jednowątkowych. Gdy dodawane są nowe wątki, menedżer sterty przypisuje im areny pomocnicze w celu zmniejszenia rywalizacji. Najpierw próbuje przypisać każdy nowy wątek do nieużytej areny, tworząc nowe, jeśli jest to konieczne, aż do limitu 2 razy liczba rdzeni CPU dla systemów 32-bitowych i 8 razy dla systemów 64-bitowych. Po osiągnięciu limitu wątki muszą dzielić areny, co prowadzi do potencjalnej rywalizacji.

W przeciwieństwie do głównej areny, która rozszerza się za pomocą wywołania systemowego brk, areny pomocnicze tworzą "substerty" za pomocą mmap i mprotect, aby symulować zachowanie sterty, umożliwiając elastyczne zarządzanie pamięcią dla operacji wielowątkowych.

Substerty

Substerty służą jako rezerwy pamięci dla aren pomocniczych w aplikacjach wielowątkowych, pozwalając im rosnąć i zarządzać swoimi własnymi obszarami sterty oddzielnie od głównej sterty. Oto w jaki sposób substerty różnią się od początkowej sterty i jak działają:

Początkowa sterta vs. substerty:

Początkowa sterta znajduje się bezpośrednio po binarnym pliku programu w pamięci i rozszerza się za pomocą wywołania systemowego sbrk.
Substerty, używane przez areny pomocnicze, są tworzone za pomocą mmap, wywołania systemowego mapującego określony obszar pamięci.

Rezerwacja pamięci za pomocą mmap:

Gdy menedżer sterty tworzy substertę, rezerwuje duży blok pamięci za pomocą mmap. Rezerwacja ta nie alokuje pamięci natychmiast; po prostu oznacza obszar, którego inne procesy systemowe lub alokacje nie powinny używać.
Domyślny rozmiar rezerwacji dla substerty wynosi 1 MB dla procesów 32-bitowych i 64 MB dla procesów 64-bitowych.

Stopniowe rozszerzanie za pomocą mprotect:

Początkowo zarezerwowany obszar pamięci jest oznaczony jako PROT_NONE, co oznacza, że jądro nie musi jeszcze alokować pamięci fizycznej dla tego obszaru.
Aby "rozszerzyć" substertę, menedżer sterty używa mprotect, aby zmienić uprawnienia strony z PROT_NONE na PROT_READ | PROT_WRITE, co skutkuje alokacją pamięci fizycznej dla wcześniej zarezerwowanych adresów. Ten krok po kroku pozwala substercie rosnąć w miarę potrzeb.
Gdy cała substerta zostanie wyczerpana, menedżer sterty tworzy nową substertę, aby kontynuować alokację.

Metadane

Jak wspomniano wcześniej, te bloki posiadają również pewne metadane, bardzo dobrze przedstawione na tym obrazie:

Metadane zazwyczaj wynoszą 0x08B, co wskazuje na bieżący rozmiar bloku, używając ostatnich 3 bitów do wskazania:

A: Jeśli 1, pochodzi z substerty, jeśli 0, jest w głównej arenie
M: Jeśli 1, ten blok jest częścią przestrzeni zaalokowanej za pomocą mmap i nie jest częścią sterty
P: Jeśli 1, poprzedni blok jest używany

Następnie miejsce na dane użytkownika, a na końcu 0x08B wskazujący na rozmiar poprzedniego bloku, gdy blok jest dostępny (lub do przechowywania danych użytkownika, gdy jest zaalokowany).

Ponadto, gdy jest dostępne, dane użytkownika służą również do przechowywania pewnych danych:

Wskaźnik do następnego bloku
Wskaźnik do poprzedniego bloku
Rozmiar następnego bloku na liście
Rozmiar poprzedniego bloku na liście

Zauważ, jak ułożenie listy w ten sposób eliminuje potrzebę posiadania tablicy, w której każdy pojedynczy blok jest rejestrowany.

Ochrona przed zwalnianiem

Aby chronić się przed przypadkowym lub zamierzonym nadużyciem funkcji free, przed wykonaniem jej działań wykonuje pewne sprawdzenia:

Sprawdza, czy adres jest wyrównany do granicy 8 bajtów lub 16 bajtów w przypadku 64-bitowej granicy ((address % 16) == 0), ponieważ malloc zapewnia, że wszystkie alokacje są wyrównane.
Sprawdza, czy pole rozmiaru bloku nie jest niemożliwe – albo dlatego, że jest zbyt małe, zbyt duże, nie jest wyrównane, lub zachodziłoby na koniec przestrzeni adresowej procesu.
Sprawdza, czy blok znajduje się w granicach areny.
Sprawdza, czy blok nie jest już oznaczony jako wolny, sprawdzając odpowiadający bit „P” znajdujący się w metadanych na początku następnego bloku.

Bins

Aby poprawić efektywność przechowywania fragmentów, każdy fragment nie jest przechowywany tylko w jednej liście połączonej, ale istnieje kilka typów. Są to pojemniki, a istnieje 5 typów pojemników: 62 małe pojemniki, 63 duże pojemniki, 1 pojemnik niesortowany, 10 szybkich pojemników i 64 pojemniki tcache na wątek.

Początkowy adres dla każdego pojemnika niesortowanego, małego i dużego znajduje się w tej samej tablicy. Indeks 0 jest nieużywany, 1 to pojemnik niesortowany, pojemniki 2-64 to małe pojemniki, a pojemniki 65-127 to duże pojemniki.

Małe pojemniki

Małe pojemniki są szybsze niż duże pojemniki, ale wolniejsze niż szybkie pojemniki.

Każdy pojemnik spośród 62 będzie zawierał fragmenty o tej samej wielkości: 16, 24, ... (z maksymalną wielkością 504 bajtów w systemie 32-bitowym i 1024 w systemie 64-bitowym). Pomaga to w szybkości znajdowania pojemnika, w którym powinno być przydzielone miejsce oraz w wstawianiu i usuwaniu wpisów na tych listach.

Duże pojemniki

W przeciwieństwie do małych pojemników, które zarządzają fragmentami o stałych rozmiarach, każdy duży pojemnik obsługuje zakres rozmiarów fragmentów. Jest to bardziej elastyczne, pozwalając systemowi na dostosowanie się do różnych rozmiarów bez konieczności posiadania osobnego pojemnika dla każdego rozmiaru.

W alokatorze pamięci duże pojemniki zaczynają tam, gdzie kończą się małe pojemniki. Zakresy dla dużych pojemników rosną stopniowo, co oznacza, że pierwszy pojemnik może obejmować fragmenty od 512 do 576 bajtów, podczas gdy kolejny obejmuje od 576 do 640 bajtów. Ten wzorzec kontynuuje się, a największy pojemnik zawiera wszystkie fragmenty 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ę fragmentów o różnych rozmiarach, aby znaleźć najlepsze dopasowanie do alokacji. Gdy fragment jest wstawiany do dużego pojemnika, musi być posortowany, a podczas alokacji pamięci system musi znaleźć odpowiedni fragment. 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
16 pojemników o zakresie 512B
8 pojemników o zakresie 4096B
4 pojemniki o zakresie 32768B
2 pojemniki o zakresie 262144B
1 pojemnik na pozostałe rozmiary

Pojemnik niesortowany

Pojemnik niesortowany to szybka pamięć podręczna używana przez menedżera sterty do przyspieszenia alokacji pamięci. Oto jak to działa: gdy program zwalnia pamięć, menedżer sterty nie umieszcza jej od razu w konkretnym pojemniku. Zamiast tego najpierw próbuje połączyć ją z sąsiednimi wolnymi fragmentami, aby utworzyć większy blok wolnej pamięci. Następnie umieszcza ten nowy fragment w ogólnym pojemniku o nazwie "pojemnik niesortowany".

Gdy program prosi o pamięć, menedżer sterty najpierw sprawdza pojemnik niesortowany, aby zobaczyć, czy jest tam fragment odpowiedniego rozmiaru. Jeśli znajdzie taki, używa go od razu, co jest szybsze niż przeszukiwanie innych pojemników. Jeśli nie znajdzie odpowiedniego fragmentu, przenosi zwolnione fragmenty do odpowiednich pojemników, małych lub dużych, w zależności od ich rozmiaru.

Więc pojemnik niesortowany to sposób przyspieszenia alokacji pamięci poprzez szybkie ponowne wykorzystanie niedawno zwolnionej pamięci i zmniejszenie potrzeby czasochłonnego przeszukiwania i łączenia.

Zauważ, że nawet jeśli fragmenty należą do różnych kategorii, od czasu do czasu, jeśli dostępny fragment koliduje z innym dostępnym fragmentem (nawet jeśli są one z różnych kategorii), zostaną one połączone.

Szybkie pojemniki

Szybkie pojemniki są zaprojektowane, aby przyspieszyć alokację pamięci dla małych fragmentów, trzymając niedawno zwolnione fragmenty w strukturze szybkiego dostępu. Te pojemniki używają podejścia Last-In, First-Out (LIFO), co oznacza, że najnowszy zwolniony fragment jest pierwszy, który jest ponownie używany, gdy występuje nowe żądanie alokacji. To zachowanie jest korzystne dla szybkości, ponieważ szybciej jest wstawiać i usuwać z góry stosu (LIFO) w porównaniu z kolejką (FIFO).

Dodatkowo, szybkie pojemniki używają list jednokierunkowych, a nie dwukierunkowych, co dodatkowo poprawia szybkość. Ponieważ fragmenty w szybkich pojemnikach nie są łączone z sąsiadami, nie ma potrzeby skomplikowanej struktury, która umożliwia usuwanie ze środka. Lista jednokierunkowa jest prostsza i szybsza dla tych operacji.

W zasadzie, to co się dzieje tutaj, 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 do aktualnie dostępnego fragmentu, a adres tego nowo zwolnionego fragmentu zostanie umieszczony w nagłówku.

Fragmenty w szybkich pojemnikach nie są automatycznie ustawiane jako dostępne, więc pozostają jako fragmenty szybkich pojemników przez pewien czas zamiast móc łączyć się z innymi fragmentami.

Pojemniki Tcache (Pamięć podręczna na wątek)

Mimo że wątki starają się mieć swoją własną stertę (zobacz Areny i Podsterty), istnieje możliwość, że proces z wieloma wątkami (np. serwer sieciowy) 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 podobne do szybkiego pojemnika na wątek w taki sposób, że jest to lista jednokierunkowa, która nie łączy fragmentów. Każdy wątek ma 64 jednokierunkowe pojemniki tcache. Każdy pojemnik może zawierać maksymalnie 7 fragmentów tego samego rozmiaru o rozmiarach od 24 do 1032B w systemach 64-bitowych i od 12 do 516B w systemach 32-bitowych.

Gdy wątek zwalnia fragment, jeśli nie jest zbyt duży do alokacji w tcache i odpowiedni pojemnik tcache nie jest pełny (już 7 fragmentów), zostanie tam zaalokowany. Jeśli nie może trafić do tcache, będzie musiał czekać na blokadę sterty, aby móc wykonać operację zwolnienia globalnie.

Gdy fragment jest alokowany, jeśli istnieje wolny fragment potrzebnego rozmiaru w tcache, zostanie on użyty, jeśli nie, będzie musiał czekać na blokadę sterty, aby znaleźć go w globalnych pojemnikach lub utworzyć nowy. Istnieje również optymalizacja, w tym przypadku, podczas posiadania blokady sterty, wątek wypełni swoje tcache fragmentami sterty (7) o żądanym rozmiarze, więc w przypadku potrzeby więcej, znajdzie je w tcache.

Kolejność pojemników

Dla alokacji:

Jeśli dostępny kawałek w Tcache o takim rozmiarze, użyj Tcache
Jeśli jest bardzo duży, użyj mmap
Uzyskaj blokadę sterty areny i:
Jeśli dostępny jest wystarczająco mały kawałek w fast binie o żądanym rozmiarze, użyj go i wypełnij tcache z fast binu
Sprawdź każdy wpis na liście nieposortowanej, szukając kawałka wystarczająco dużego i wypełnij tcache, jeśli to możliwe
Sprawdź małe pojemniki lub duże pojemniki (zgodnie z żądanym rozmiarem) i wypełnij tcache, jeśli to możliwe
Utwórz nowy kawałek z dostępnej pamięci
Jeśli nie ma dostępnej pamięci, pobierz więcej za pomocą sbrk
Jeśli pamięć głównej sterty nie może się powiększyć, utwórz nową przestrzeń za pomocą mmap
Jeśli nic nie zadziałało, zwróć null

Dla zwalniania:

Jeśli wskaźnik jest Null, zakończ
Wykonaj sprawdzenia spójności free w kawałku, aby spróbować zweryfikować, czy to autentyczny kawałek
Jeśli jest wystarczająco mały i tcache nie jest pełne, umieść go tam
Jeśli ustawiony jest bit M (nie sterta), użyj munmap
Uzyskaj blokadę sterty areny:
Jeśli pasuje do fastbinu, umieść go tam
Jeśli kawałek jest > 64KB, natychmiast scal fastbiny i umieść wynikowe połączone kawałki na liście nieposortowanej.
Scal kawałek wstecz i naprzód z sąsiednimi zwolnionymi kawałkami w małych, dużych i nieposortowanych pojemnikach, jeśli takie istnieją.
Jeśli jest na szczycie sterty, scal go z nieużywaną pamięcią
Jeśli nie pasuje do poprzednich, przechowaj go na liście nieposortowanej

Szybki przykład sterty z https://guyinatuxedo.github.io/25-heap/index.html ale w arm64:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void main(void)
{
char *ptr;
ptr = malloc(0x10);
strcpy(ptr, "panda");
}

Ustaw punkt przerwania na końcu funkcji main i sprawdźmy, gdzie przechowywane były informacje:

Można zauważyć, że ciąg znaków panda został przechowywany pod adresem 0xaaaaaaac12a0 (który był adresem podanym jako odpowiedź przez malloc wewnątrz x0). Sprawdzając 0x10 bajtów przed nim, można zobaczyć, że 0x0 oznacza, że poprzedni blok nie jest używany (długość 0) i że długość tego bloku to 0x21.

Dodatkowe miejsce zarezerwowane (0x21-0x10=0x11) pochodzi z dodanych nagłówków (0x10), a 0x1 nie oznacza, że zarezerwowano 0x21 bajtów, ale ostatnie 3 bity długości bieżącego nagłówka mają pewne specjalne znaczenia. Ponieważ długość zawsze jest wyrównana do 16 bajtów (w maszynach 64-bitowych), te bity faktycznie nigdy nie zostaną użyte przez liczbę długości.

0x1:     Previous in Use     - Specifies that the chunk before it in memory is in use
0x2:     Is MMAPPED          - Specifies that the chunk was obtained with mmap()
0x4:     Non Main Arena      - Specifies that the chunk was obtained from outside of the main arena

Odnośniki

PreviousFormat Strings Template NextUse After Free

Last updated 1 hour ago