Da bi se poboljšala efikasnost načina na koji su delovi memorije smešteni, svaki deo memorije nije samo u jednoj povezanoj listi, već postoje različite vrste. To su "bins" i postoji 5 vrsta "bins": 62 mali "bins", 63 velika "bins", 1 nesortirani "bin", 10 brzih "bins" i 64 "tcache bins" po niti.
Početna adresa za svaki nesortirani, mali i veliki "bin" je unutar istog niza. Indeks 0 se ne koristi, 1 je nesortirani "bin", "bins" 2-64 su mali "bins" i "bins" 65-127 su veliki "bins".
Tcache (Keš po niti) "Bins"
Iako niti pokušavaju da imaju svoj sopstveni "heap" (videti Arenas i Subheaps), postoji mogućnost da proces sa puno niti (kao što je veb server) će deliti "heap" sa drugim nitima. U tom slučaju, glavno rešenje je korišćenje brava, što može znatno usporiti niti.
Kada nit oslobodi deo memorije, ako nije prevelik da bi bio dodeljen u "tcache" i odgovarajući "tcache bin" nije pun (već ima 7 delova), biće dodeljen tamo. Ako ne može ići u "tcache", moraće da sačeka da se "heap lock" oslobodi kako bi mogao da izvrši globalnu operaciju oslobađanja.
Kada se deo memorije dodeli, ako postoji slobodan deo potrebne veličine u Tcache-u, biće korišćen, ako ne, moraće da sačeka da se "heap lock" oslobodi kako bi mogao da pronađe jedan u globalnim "bins" ili da napravi novi.
Postoji i optimizacija, u ovom slučaju, dok ima "heap lock", nit će popuniti svoj Tcache sa delovima "heap" (7) tražene veličine, tako da ako mu je potrebno više, moći će da ih pronađe u Tcache-u.
Dodaj primer tcache dela
```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; }
Kompajlirajte ga i debagujte sa prekidnom tačkom u ret opcode-u iz glavne funkcije. Zatim, pomoću gef-a možete videti tcache bin u upotrebi:
```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)
Tcache Strukture i Funkcije
U sledećem kodu je moguće videti maksimalne binove i delove po indeksu, strukturu tcache_entry kreiranu da bi se izbeglo duplo oslobađanje i tcache_perthread_struct, strukturu koju svaka nit koristi da bi sačuvala adrese za svaki indeks bin-a.
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */# defineTCACHE_MAX_BINS64# defineMAX_TCACHE_SIZEtidx2usize (TCACHE_MAX_BINS-1)/* Only used to pre-fill the tunables. */# definetidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)/* When "x" is from chunksize(). */# definecsize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT -1) / MALLOC_ALIGNMENT)/* When "x" is a user-provided size. */# defineusize2tidx(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..20idx 2 bytes 41..56 or 21..28etc. *//* This is another arbitrary limit, which tunables can change. Eachtcache bin will hold at most this number of chunks. */# defineTCACHE_FILL_COUNT7/* Maximum chunks in tcache bins for tunables. This value must fit the rangeof tcache->counts[] entries, else they may overflow. */# defineMAX_TCACHE_COUNT UINT16_MAX[...]typedefstruct 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 theper-thread cache (hence "tcache_perthread_struct"). Keepingoverall size low is mildly important. Note that COUNTS and ENTRIESare redundant (we could have just counted the linked list eachtime), this is for performance reasons. */typedefstruct tcache_perthread_struct{uint16_t counts[TCACHE_MAX_BINS];tcache_entry *entries[TCACHE_MAX_BINS];} tcache_perthread_struct;
Funkcija __tcache_init je funkcija koja kreira i alocira prostor za objekat tcache_perthread_struct
// From https://github.com/bminor/glibc/blob/f942a732d37a96217ef828116ebe64a644db18d7/malloc/malloc.c#L3241C1-L3274C2staticvoidtcache_init(void){mstate ar_ptr;void*victim =0;constsize_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, wetypically do this very early, so either there is sufficientmemory, or there isn't enough memory to do non-trivialallocations anyway. */if (victim){tcache = (tcache_perthread_struct *) victim;memset (tcache,0,sizeof (tcache_perthread_struct));}}
Tcache Indeksi
Tcache ima nekoliko binova u zavisnosti od veličine, a početni pokazivači na prvi blok svakog indeksa i količina blokova po indeksu se nalaze unutar bloka. To znači da je moguće pronaći sve početne tačke tcache-a i količinu Tcache blokova lociranjem bloka sa ovim informacijama (obično prvi).
Brzi binovi
Brzi binovi su dizajnirani da ubrzaju dodelu memorije za male blokove čuvanjem nedavno oslobođenih blokova u strukturi sa brzim pristupom. Ovi binovi koriste pristup poslednji unutra, prvi napolje (LIFO) pristup, što znači da je najskorije oslobođeni blok prvi koji će biti ponovo korišćen kada postoji nova zahtev za alokacijom. Ovo ponašanje je korisno za brzinu, jer je brže ubaciti i ukloniti sa vrha steka (LIFO) u poređenju sa redom (FIFO).
Dodatno, brzi binovi koriste jednostruko povezane liste, a ne dvostruko povezane, što dodatno poboljšava brzinu. Pošto se blokovi u brzim binovima ne spajaju sa susedima, nema potrebe za složenom strukturom koja omogućava uklanjanje iz sredine. Jednostruko povezana lista je jednostavnija i brža za ove operacije.
U osnovi, ono što se dešava ovde je da je zaglavlje (pokazivač na prvi blok koji treba proveriti) uvek usmereno ka poslednjem oslobođenom bloku te veličine. Dakle:
Kada se alocira novi blok te veličine, zaglavlje pokazuje na slobodan blok za korišćenje. Pošto ovaj slobodan blok pokazuje na sledeći koji treba koristiti, ova adresa je sačuvana u zaglavlju tako da sledeća alokacija zna gde da dobije dostupan blok
Kada se blok oslobodi, slobodan blok će sačuvati adresu trenutno dostupnog bloka i adresa ovog novootvorenog bloka će biti stavljena u zaglavlje
Maksimalna veličina povezane liste je 0x80 i organizovane su tako da će blok veličine 0x20 biti u indeksu 0, blok veličine 0x30 bi bio u indeksu 1...
Blokovi u brzim binovima nisu označeni kao dostupni tako da se čuvaju kao blokovi brzih binova neko vreme umesto što bi mogli da se spoje sa drugim slobodnim blokovima koji ih okružuju.
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711/*FastbinsAn array of lists holding recently freed small chunks. Fastbinsare not doubly linked. It is faster to single-link them, andsince chunks are never removed from the middles of these lists,double linking is not necessary. Also, unlike regular bins, theyare not even processed in FIFO order (they use faster LIFO) sinceordering doesn't much matter in the transient contexts in whichfastbins are normally used.Chunks in fastbins keep their inuse bit set, so they cannotbe consolidated with other free chunks. malloc_consolidatereleases all chunks in fastbins and consolidates them withother free chunks.*/typedefstruct malloc_chunk *mfastbinptr;#definefastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])/* offset 2 to use otherwise unindexable first 2 bins */#definefastbin_index(sz) \((((unsignedint) (sz)) >> (SIZE_SZ ==8?4:3)) -2)/* The maximum fastbin request size we support */#defineMAX_FAST_SIZE (80* SIZE_SZ /4)#defineNFASTBINS (fastbin_index (request2size (MAX_FAST_SIZE)) +1)
Dodajte primer brze binarne čestice
```c #include #include
int main(void) { char *chunks[8]; int i;
// Loop to allocate memory 8 times for (i = 0; i < 8; i++) { chunks[i] = malloc(24); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }
// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }
return 0; }
Zabeležite kako alociramo i oslobađamo 8 blokova iste veličine tako da popunjavaju tcache, a osmi je smešten u brzi blok.
Kompajlirajte i debagujte sa prekidnom tačkom u `ret` opkodu iz `main` funkcije. Zatim, pomoću `gef` alata možete videti da je tcache bin pun i da je jedan blok u brzom binu:
```bash
gef➤ heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=7] ← Chunk(addr=0xaaaaaaac1770, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac1750, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac1730, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac1710, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac16f0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac16d0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] ← Chunk(addr=0xaaaaaaac1790, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
Fastbins[idx=1, size=0x30] 0x00
Neuređena kanta
Neuređena kanta je keš koji koristi menadžer hipa kako bi ubrzao dodelu memorije. Evo kako funkcioniše: Kada program oslobodi komad, i ako taj komad ne može biti dodeljen u tcache ili brzoj kanti i ne sudara se sa vršnim komadom, menadžer hipa ga ne stavlja odmah u određenu malu ili veliku kantu. Umesto toga, prvo pokušava da ga spoji sa bilo kojim susednim slobodnim komadima kako bi stvorio veći blok slobodne memorije. Zatim, smešta ovaj novi komad u opštu kantu nazvanu "neuređena kanta".
Kada program zatraži memoriju, menadžer hipa proverava neuređenu kantu da vidi da li postoji dovoljno veliki komad. Ako pronađe jedan, odmah ga koristi. Ako ne pronađe odgovarajući komad u neuređenoj kanti, premestiće sve komade sa ove liste u njihove odgovarajuće kante, bilo male ili velike, na osnovu njihove veličine.
Imajte na umu da ako se veći komad podeli na 2 polovine i preostali deo je veći od MINSIZE, biće vraćen nazad u neuređenu kantu.
Dakle, neuređena kanta je način da se ubrza dodela memorije brzim ponovnim korišćenjem nedavno oslobođene memorije i smanjenjem potrebe za dugotrajnim pretragama i spajanjima.
Imajte na umu da čak i ako su komadi različitih kategorija, ako dostupan komad sudara sa drugim dostupnim komadom (čak i ako su originalno pripadali različitim kantama), biće spojeni.
Mali Bins
Mali binovi su brži od velikih binova, ali sporiji od brzih binova.
Svaki bin od 62 će imati blokove iste veličine: 16, 24, ... (sa maksimalnom veličinom od 504 bajta u 32 bitnom i 1024 u 64 bitnom režimu). Ovo pomaže u brzini pronalaženja binova gde treba alocirati prostor i ubacivanju i uklanjanju unosa sa ovih lista.
Ovako se računa veličina malog bina prema indeksu bina:
Najmanja veličina: 2*4*indeks (npr. indeks 5 -> 40)
Najveća veličina: 2*8*indeks (npr. indeks 5 -> 80)
// Loop to allocate memory 8 times for (i = 0; i < 9; i++) { chunks[i] = malloc(0x100); if (chunks[i] == NULL) { // Check if malloc failed fprintf(stderr, "Memory allocation failed at iteration %d\n", i); return 1; } printf("Address of chunk %d: %p\n", i, (void *)chunks[i]); }
// Loop to free the allocated memory for (i = 0; i < 8; i++) { free(chunks[i]); }
chunks[9] = malloc(0x110);
return 0; }
Primetite kako alociramo i oslobađamo 9 blokova iste veličine tako da **popunimo tcache** i osmi je smešten u unsorted bin jer je **prevelik za fastbin**, a deveti nije oslobođen tako da deveti i osmi **ne budu spojeni sa vršnim blokom**. Zatim alociramo veći blok od 0x110 što dovodi do toga da **blok u unsorted binu pređe u small bin**.
Kompajlirajte i debagujte sa prekidnom tačkom u `ret` opcode-u iz `main` funkcije. Zatim, pomoću `gef` alata možete videti da je tcache bin pun i da je jedan blok u small binu:
```bash
gef➤ heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=15, size=0x110, count=7] ← Chunk(addr=0xaaaaaaac1d10, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac1c00, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac1af0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac19e0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac18d0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac17c0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← Chunk(addr=0xaaaaaaac12a0, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x20] 0x00
Fastbins[idx=1, size=0x30] 0x00
Fastbins[idx=2, size=0x40] 0x00
Fastbins[idx=3, size=0x50] 0x00
Fastbins[idx=4, size=0x60] 0x00
Fastbins[idx=5, size=0x70] 0x00
Fastbins[idx=6, size=0x80] 0x00
─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] small_bins[16]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→ Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in 1 small non-empty bins.
Velike kante
Za razliku od malih kanti, koje upravljaju komadićima fiksnih veličina, svaka velika kanta obrađuje opseg veličina komadića. Ovo je fleksibilnije, omogućavajući sistemu da se prilagodi različitim veličinama bez potrebe za posebnom kantom za svaku veličinu.
U alokatoru memorije, velike kante počinju tamo gde se završavaju male kante. Opsezi za velike kante postaju sve veći, što znači da prva kanta može obuhvatiti komadiće od 512 do 576 bajtova, dok sledeća obuhvata 576 do 640 bajtova. Ovaj obrazac se nastavlja, pri čemu najveća kanta sadrži sve komadiće iznad 1MB.
Velike kante sporije rade u poređenju sa malim kantama jer moraju sortirati i pretraživati listu različitih veličina komadića kako bi pronašle najbolje odgovarajući za alokaciju. Kada se komadić ubaci u veliku kantu, mora biti sortiran, a prilikom alokacije memorije, sistem mora pronaći odgovarajući komadić. Ovaj dodatni rad ih čini sporijim, ali budući da su velike alokacije manje uobičajene od malih, to je prihvatljiva trgovina.
Postoje:
32 kante opsega 64B (sudaraju se sa malim kantama)
16 kanti opsega 512B (sudaraju se sa malim kantama)
8 kanti opsega 4096B (delimično se sudaraju sa malim kantama)
4 kante opsega 32768B
2 kante opsega 262144B
1 kanta za preostale veličine
Kod veličina velikih kanti
```c // From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
</details>
<details>
<summary>Dodajte primer velikog bloka</summary>
```c
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
char *chunks[2];
chunks[0] = malloc(0x1500);
chunks[1] = malloc(0x1500);
free(chunks[0]);
chunks[0] = malloc(0x2000);
return 0;
}
Izvrše se 2 velike alokacije, zatim se jedna oslobađa (stavlja se u unsorted bin) i vrši se veća alokacija (premeštanje oslobođene u unsorted bin u large bin).
Kompajlirajte to i debagujte sa prekidnom tačkom u ret opcode-u iz main funkcije. Zatim, pomoću gef alata možete videti da je tcache bin pun i da je jedan chunk u large bin-u:
gef➤heapbin──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Alltcachebinsareempty───────────────────────────────────────────────────────────────────────── Fastbins for arena at 0xfffff7f90b00 ─────────────────────────────────────────────────────────────────────────
Fastbins[idx=0,size=0x20]0x00Fastbins[idx=1,size=0x30]0x00Fastbins[idx=2,size=0x40]0x00Fastbins[idx=3,size=0x50]0x00Fastbins[idx=4,size=0x60]0x00Fastbins[idx=5,size=0x70]0x00Fastbins[idx=6,size=0x80]0x00─────────────────────────────────────────────────────────────────────── Unsorted Bin for arena at 0xfffff7f90b00 ───────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.──────────────────────────────────────────────────────────────────────── Small Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.──────────────────────────────────────────────────────────────────────── Large Bins for arena at 0xfffff7f90b00 ────────────────────────────────────────────────────────────────────────
[+] large_bins[100]: fw=0xaaaaaaac1290, bk=0xaaaaaaac1290→Chunk(addr=0xaaaaaaac12a0, size=0x1510, flags=PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)[+] Found 1 chunks in 1 large non-empty bins.
Vrhunski blok
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711/*TopThe top-most available chunk (i.e., the one bordering the end ofavailable memory) is treated specially. It is never included inany bin, is used only if no other chunk is available, and isreleased back to the system if it is very large (seeM_TRIM_THRESHOLD). Because top initiallypoints to its own bin with initial zero size, thus forcingextension on the first malloc request, we avoid having any specialcode in malloc to check whether it even exists yet. But we stillneed to do so when getting memory from system, so we makeinitial_top treat the bin as a legal but unusable chunk during theinterval between initialization and the first call tosysmalloc. (This is somewhat delicate, since it relies onthe 2 preceding words to be zero during this interval as well.)*//* Conveniently, the unsorted bin can be used as dummy top on first call */#defineinitial_top(M) (unsorted_chunks (M))
Osnovno, ovo je deo koji sadrži sav trenutno dostupan heap. Kada se izvrši malloc, ako nema dostupnog slobodnog chunk-a za korišćenje, ovaj top chunk će smanjiti svoju veličinu pružajući potreban prostor. Pokazivač na Top Chunk se čuva u strukturi malloc_state.
Osim toga, na početku je moguće koristiti nesortirani chunk kao top chunk.
Posmatrajte primer Top Chunk-a
```c #include #include
int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); return 0; }
Gde se može videti da je vrhunski blok na adresi 0xaaaaaaac1ae0. To nije iznenađenje jer je poslednji alocirani blok bio na 0xaaaaaaac12a0 sa veličinom 0x410 i 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0.
Takođe je moguće videti dužinu vrhunskog bloka na njegovom zaglavlju bloka:
Kada se koristi malloc i deo je podeljen (na primer iz nesortirane kante ili iz vršnog bloka), deo koji je kreiran od preostalog dela podeljenog bloka naziva se Poslednji ostatak i njegov pokazivač se čuva u strukturi malloc_state.
