Jak działa malloc
Sterta i listy wolnych bloków.
Jak działa malloc to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Co naprawdę robi malloc
Po wywołaniu malloc(n) biblioteka C przekazuje wskaźnik do co najmniej n użytecznych bajtów. Sterta jest jednak tylko obszarem pamięci procesu zarządzanym przez alokator.
Zadaniem alokatora jest prowadzenie ewidencji: śledzenie używanych i wolnych bajtów oraz efektywne ponowne wykorzystywanie zwolnionej pamięci.
Sterta pochodzi z systemu operacyjnego
Alokator nie tworzy pamięci z niczego. Prosi system operacyjny o duże fragmenty za pomocą wywołań systemowych, takich jak brk/sbrk lub mmap.
Następnie dzieli te fragmenty na mniejsze bloki na potrzeby wywołań malloc. Pytanie systemu operacyjnego o pamięć jest kosztowne, dlatego alokatory pobierają ją partiami i poddają recyklingowi.
/* Conceptual: grow the heap by 4096 bytes */
void *base = sbrk(4096);
if (base == (void *)-1) {
/* out of memory */
}sbrk i granica programu
sbrk(n) przesuwa „granicę programu” o n bajtów w górę i zwraca jej poprzednie położenie. Nowo udostępniony obszar staje się dostępnym miejscem na stercie.
To rozwiązanie jest liniowe i proste, ale nie pozwala łatwo zwracać pamięci ze środka obszaru. Współczesne alokatory preferują mmap dla dużych żądań.
void *prev_break = sbrk(0); /* current break */
sbrk(1024); /* grow by 1 KB */
/* prev_break now points to fresh memory */Metadane bloku
Dla każdej alokacji alokator przechowuje obok danych mały nagłówek: rozmiar oraz informację, czy blok jest wolny. Ten nagłówek pozwala funkcji free działać wyłącznie na przekazanym jej wskaźniku do danych.
Otrzymany z malloc wskaźnik wskazuje miejsce za nagłówkiem, więc metadane pozostają przed użytkownikiem ukryte.
typedef struct block {
size_t size;
int free;
struct block *next;
} block_t;Wskaźnik tuż za nagłówkiem
Typową sztuczką jest arytmetyka wskaźników: wskaźnik użytkownika to header + 1. Mając wskaźnik użytkownika, nagłówek znajduje się o jeden block_t przed nim.
W ten sposób free(p) odzyskuje rozmiar zaalokowanego bloku, mimo że nie trzeba go dodatkowo przekazywać.
block_t *hdr = (block_t *)user_ptr - 1;
printf("block size = %zu\n", hdr->size);Przykład układu małego nagłówka
Umieśćmy nagłówek w statycznym buforze i odczytajmy go ponownie. Pokazuje to, jak rzeczywisty alokator dzieli obszar na nagłówek i dane.
Nie są wykonywane żadne wywołania systemu operacyjnego, więc program działa wszędzie.
#include <stdio.h>
#include <stddef.h>
typedef struct { size_t size; int free; } block_t;
static char buffer[256];
int main(void) {
block_t *h = (block_t *)buffer;
h->size = 64;
h->free = 0;
void *payload = (char *)buffer + sizeof(block_t);
printf("header bytes = %zu\n", sizeof(block_t));
printf("payload offset = %ld\n", (long)((char *)payload - buffer));
printf("size field = %zu\n", h->size);
return 0;
}Idea listy wolnych bloków
Wiele alokatorów łączy wolne bloki w listę jednokierunkową. Gdy wywołujesz malloc, alokator przeszukuje tę listę w poszukiwaniu wystarczająco dużego bloku.
Gdy wywołujesz free, blok zostaje oznaczony jako wolny i zwrócony na listę do późniejszego ponownego użycia, co pozwala uniknąć kolejnego żądania do systemu operacyjnego.
block_t *find_free(block_t *head, size_t size) {
block_t *b = head;
while (b && !(b->free && b->size >= size))
b = b->next;
return b;
}Co musi robić free
free(p) odnajduje nagłówek dla p, oznacza blok jako wolny i w miarę możliwości łączy go z sąsiednimi wolnymi blokami (koalescencja), aby ograniczyć fragmentację.
Dwukrotne wywołanie free dla tego samego wskaźnika lub zwolnienie wskaźnika, który nie pochodzi ze sterty, powoduje niezdefiniowane zachowanie, ponieważ metadane zostają uszkodzone.
void my_free(void *p) {
if (!p) return;
block_t *hdr = (block_t *)p - 1;
hdr->free = 1;
/* real allocators coalesce neighbors here */
}Fragmentacja
Z czasem zwalnianie i alokowanie bloków o różnych rozmiarach pozostawia luki. Fragmentacja zewnętrzna oznacza, że wolna pamięć istnieje, ale jest rozproszona w kawałkach zbyt małych, by spełnić żądanie.
Fragmentacja wewnętrzna to zmarnowane miejsce wewnątrz bloku większego niż wymagany, często wynikające z wyrównania lub zaokrąglania.
Wymagania dotyczące wyrównania
malloc musi zwracać pamięć wyrównaną odpowiednio dla każdego typu. Na większości systemów 64-bitowych oznacza to wyrównanie do 16 bajtów, spełniające wymagania max_align_t.
Niewyrównane wskaźniki mogą powodować awarie na niektórych procesorach lub spowalniać dostęp na innych, dlatego alokatory zawsze zaokrąglają rozmiar danych do granicy wyrównania.
#include <stdalign.h>
/* alignof(max_align_t) is the strictest required alignment */
size_t a = alignof(max_align_t);Połączenie wszystkich elementów
Minimalny alokator potrzebuje zatem: źródła pamięci (statycznego bufora, sbrk lub mmap), nagłówków dla poszczególnych bloków, strategii znajdowania wolnego miejsca oraz obsługi wyrównania.
W kolejnych lekcjach zbudujemy te elementy: najpierw alokator bump, następnie listy wolnych bloków, a na końcu obsługę wyrównania i dzielenie bloków.
/* The four pillars of a custom allocator */
/* 1. memory source 2. block headers */
/* 3. free-block search 4. alignment */Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat wewnętrznego działania alokatora.
Podsumowanie
malloc zarządza stertą uzyskaną z systemu operacyjnego za pomocą sbrk lub mmap, dzieląc ją na bloki z ukrytymi nagłówkami, które śledzą rozmiar i stan wolny.
Listy wolnych bloków umożliwiają ponowne użycie pamięci, wyrównanie zapewnia poprawną obsługę każdego typu, a fragmentacja jest głównym wyzwaniem. Te idee stanowią podstawę alokatora, który zbudujemy dalej.
Często zadawane pytania
Czy lekcja „Jak działa malloc” jest bezpłatna?
Tak — pełny tekst „Jak działa malloc” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Jak działa malloc”?
Sterta i listy wolnych bloków. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Jak działa malloc”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.