Om die doeltreffendheid van hoe stukke gestoor word te verbeter, is elke stuk nie net in een gekoppelde lys nie, maar daar is verskeie tipes. Dit is die bakkies en daar is 5 tipes bakkies: 62 klein bakkies, 63 groot bakkies, 1 ongesorteerde bak, 10 vinnige bakkies en 64 tcache bakkies per draad.
Die aanvanklike adres vir elke ongesorteerde, klein en groot bakkies is binne dieselfde reeks. Die indeks 0 word nie gebruik nie, 1 is die ongesorteerde bak, bakkies 2-64 is klein bakkies en bakkies 65-127 is groot bakkies.
Tcache (Per-Draad-Kas) Bakkies
Selfs al probeer drade hul eie hoop hê (sien Arenas en Subheaps), is daar die moontlikheid dat 'n proses met baie drade (soos 'n webbediener) die hoop met ander drade sal deel. In hierdie geval is die hoofoplossing die gebruik van slotte, wat dalk die drade aansienlik verlangs.
Wanneer 'n draad 'n stuk vrymaak, as dit nie te groot is om in die tcache toegewys te word nie en die betrokke tcache bak nie vol is (reeds 7 stukke), sal dit daar toegewys word. As dit nie na die tcache kan gaan nie, sal dit moet wag vir die hoopsluiting om die vrymaakoperasie globaal uit te voer.
Wanneer 'n stuk toegewys word, as daar 'n vrye stuk van die benodigde grootte in die Tcache is, sal dit dit gebruik, indien nie, sal dit moet wag vir die hoopsluiting om een in die globale bakkies te vind of 'n nuwe een te skep.
Daar is ook 'n optimisering, in hierdie geval, terwyl die hoopsluiting het, sal die draad sy Tcache met hoopstukke (7) van die versoekte grootte vul, sodat as dit meer benodig, dit hulle in die Tcache sal vind.
Voeg 'n tcache-stukvoorbeeld by
```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; }
Kompileer dit en ontleed dit met 'n breekpunt in die ret-opkode van die hooffunksie. dan kan jy met gef die tcache-bin in gebruik sien:
```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 & Funksies
In die volgende kode is dit moontlik om die maksimum bakkies en stukke per indeks te sien, die tcache_entry struktuur wat geskep is om dubbele vrystellings te voorkom en tcache_perthread_struct, 'n struktuur wat elke draad gebruik om die adresse van elke indeks van die bakkie te stoor.
Tcache Indekse
Die tcache het verskeie bakkies afhangende van die grootte en die aanvanklike aanwysers na die eerste brokkie van elke indeks en die hoeveelheid brokkies per indeks is binne 'n brokkie geleë. Dit beteken dat deur die brokkie met hierdie inligting te vind (gewoonlik die eerste), is dit moontlik om al die tcache aanvanklike punte en die hoeveelheid Tcache brokkies te vind.
Vinnige bakkies
Vinnige bakkies is ontwerp om geheue-toekenning vir klein brokkies te versnel deur onlangs vrygestelde brokkies in 'n vinnig-toegangsstruktuur te hou. Hierdie bakkies gebruik 'n Laaste-In, Eerste-Uit (LIFO) benadering, wat beteken dat die mees onlangs vrygestelde brokkie die eerste is wat hergebruik word wanneer daar 'n nuwe toekenningsversoek is. Hierdie gedrag is voordelig vir spoed, aangesien dit vinniger is om van die boonste van 'n stok (LIFO) in te voeg en te verwyder in vergelyking met 'n ry (FIFO).
Daarbenewens gebruik vinnige bakkies enkelgelinkte lyste, nie dubbelgelinkte nie, wat die spoed verder verbeter. Aangesien brokkies in vinnige bakkies nie saamgevoeg word met bure nie, is daar geen behoefte aan 'n komplekse struktuur wat verwydering uit die middel toelaat nie. 'n Enkelgelinkte lys is eenvoudiger en vinniger vir hierdie operasies.
Basies, wat hier gebeur, is dat die kop (die aanwyser na die eerste brokkie om te kontroleer) altyd na die mees onlangs vrygestelde brokkie van daardie grootte wys. So:
Wanneer 'n nuwe brokkie van daardie grootte toegewys word, wys die kop na 'n vry brokkie om te gebruik. Aangesien hierdie vrye brokkie na die volgende een om te gebruik wys, word hierdie adres in die kop gestoor sodat die volgende toekenning weet waar om 'n beskikbare brokkie te kry
Wanneer 'n brokkie vrygestel word, sal die vrye brokkie die adres na die huidige beskikbare brokkie stoor en die adres na hierdie nuut vrygestelde brokkie sal in die kop geplaas word
Die maksimum grootte van 'n gelinkte lys is 0x80 en hulle is georganiseer sodat 'n brokkie van grootte 0x20 in indeks 0 sal wees, 'n brokkie van grootte 0x30 sou in indeks 1 wees...
Brokkies in vinnige bakkies word nie as beskikbaar ingestel nie, sodat hulle vir 'n tydperk as vinnige bin-brokkies gehou word in plaas daarvan om met ander vry brokkies om hulle te kan saamvoeg.
// 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)
Voeg 'n vinnige bin stuk voorbeeld by
#include<stdlib.h>#include<stdio.h>intmain(void){char*chunks[8];int i;// Loop to allocate memory 8 timesfor (i =0; i <8; i++) {chunks[i] =malloc(24);if (chunks[i] ==NULL) { // Check if malloc failedfprintf(stderr,"Memory allocation failed at iteration %d\n", i);return1;}printf("Address of chunk %d: %p\n", i, (void*)chunks[i]);}// Loop to free the allocated memoryfor (i =0; i <8; i++) {free(chunks[i]);}return0;}
Merk hoe ons 8 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache vul en die agtste een in die vinnige stuk gestoor word.
Kompileer dit en doen foutopsporing met 'n onderbreking in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache-bin vol is en een stuk in die vinnige bin is:
Die ongesorteerde bin is 'n cache wat deur die heap-bestuurder gebruik word om geheue-toekenning vinniger te maak. So werk dit: Wanneer 'n program 'n stuk vrymaak, en as hierdie stuk nie in 'n tcache of vinnige bin toegewys kan word en nie bots met die boonste stuk nie, plaas die heap-bestuurder dit nie dadelik in 'n spesifieke klein of groot bin nie. Eerder probeer dit om dit saam te voeg met enige aangrensende vry stukke om 'n groter blok vry geheue te skep. Dan plaas dit hierdie nuwe stuk in 'n algemene bin genaamd die "ongesorteerde bin."
Wanneer 'n program vir geheue vra, kyk die heap-bestuurder na die ongesorteerde bin om te sien of daar 'n stuk van genoeg grootte is. As dit een vind, gebruik dit dit dadelik. As dit nie 'n geskikte stuk in die ongesorteerde bin vind nie, skuif dit al die stukke in hierdie lys na hul onderskeie bakkies, klein of groot, gebaseer op hul grootte.
Let daarop dat as 'n groter stuk in 2 helftes verdeel word en die res groter as MINSIZE is, sal dit teruggeplaas word in die ongesorteerde bin.
Dus is die ongesorteerde bin 'n manier om geheue-toekenning te versnel deur onlangs vrygemaakte geheue vinnig te hergebruik en die behoefte aan tydrowende soektogte en samenvoegings te verminder.
Let daarop dat selfs as stukke van verskillende kategorieë is, as 'n beskikbare stuk bots met 'n ander beskikbare stuk (selfs as hulle oorspronklik aan verskillende bakkies behoort), sal hulle saamgevoeg word.
Voeg 'n voorbeeld van 'n ongesorteerde stuk by
```c #include #include
int main(void) { char *chunks[9]; int i;
// 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]); }
return 0; }
Merk op hoe ons 9 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache **vul** en die agtste een in die ongesorteerde binne gestoor word omdat dit **te groot is vir die fastbin** en die negende een nie vrygemaak word nie sodat die negende en die agtste **nie saamgevoeg word met die boonste stuk nie**.
Kompileer dit en ontleed dit met 'n breekpunt in die `ret` opcode van die `main` funksie. Dan kan jy met `gef` sien dat die tcache bin vol is en een stuk in die ongesorteerde bin is:
```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 ───────────────────────────────────────────────────────────────────────
[+] unsorted_bins[0]: fw=0xaaaaaaac1e10, bk=0xaaaaaaac1e10
→ Chunk(addr=0xaaaaaaac1e20, size=0x110, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[+] Found 1 chunks in unsorted bin.
Klein Bins
Klein bins is vinniger as groot bins maar stadiger as vinnige bins.
Elke bin van die 62 sal stukke van dieselfde grootte hê: 16, 24, ... (met 'n maksimum grootte van 504 byte in 32bits en 1024 in 64bits). Dit help om die bin te vind waar 'n spasie toegewys moet word en om inskrywings op hierdie lys in te voeg en te verwyder.
Dit is hoe die grootte van die klein bin bereken word volgens die indeks van die bin:
#include<stdlib.h>#include<stdio.h>intmain(void){char*chunks[10];int i;// Loop to allocate memory 8 timesfor (i =0; i <9; i++) {chunks[i] =malloc(0x100);if (chunks[i] ==NULL) { // Check if malloc failedfprintf(stderr,"Memory allocation failed at iteration %d\n", i);return1;}printf("Address of chunk %d: %p\n", i, (void*)chunks[i]);}// Loop to free the allocated memoryfor (i =0; i <8; i++) {free(chunks[i]);}chunks[9] =malloc(0x110);return0;}
Merk op hoe ons 9 stukke van dieselfde grootte toewys en vrymaak sodat hulle die tcache vul en die agtste een in die ongesorteerde bin gestoor word omdat dit te groot vir die fastbin is en die negende een nie vrygemaak word nie sodat die negende en die agtstes nie saamgevoeg word met die boonste stuk nie. Dan wys ons 'n groter stuk van 0x110 toe wat maak dat die stuk in die ongesorteerde bin na die klein bin gaan.
Kompileer dit en ontleed dit met 'n onderbreking in die ret opcode van die main funksie. Dan kan jy met gef sien dat die tcache-bin vol is en een stuk in die klein bin is:
gef➤heapbins──────────────────────────────────────────────────────────────────────────────── 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]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 ────────────────────────────────────────────────────────────────────────
[+] 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.
Groot bakkies
In teenstelling met klein bakkies, wat brokkies van vaste groottes bestuur, hanteer elke groot bak 'n reeks brokkie groottes. Dit is meer buigsaam, wat die stelsel in staat stel om verskeie groottes te akkommodeer sonder om 'n afsonderlike bak vir elke grootte nodig te hê.
In 'n geheue-toewysingsprogram begin groot bakkies waar klein bakkies eindig. Die reekse vir groot bakkies word progressief groter, wat beteken dat die eerste bak dalk brokkies van 512 tot 576 byte dek, terwyl die volgende 576 tot 640 byte dek. Hierdie patroon gaan voort, met die grootste bak wat alle brokkies bo 1MB bevat.
Groot bakkies is stadiger om te bedryf in vergelyking met klein bakkies omdat hulle moet sorteer en deur 'n lys van wisselende brokkie groottes moet soek om die beste pasgemaakte vir 'n toekenning te vind. Wanneer 'n brokkie in 'n groot bak ingevoeg word, moet dit gesorteer word, en wanneer geheue toegewys word, moet die stelsel die regte brokkie vind. Hierdie ekstra werk maak hulle stadiger, maar aangesien groot toekennings minder algemeen is as klein eenhede, is dit 'n aanvaarbare afweging.
Daar is:
32 bakkies van 64B reeks (bots met klein bakkies)
16 bakkies van 512B reeks (bots met klein bakkies)
8 bakkies van 4096B reeks (deels bots met klein bakkies)
4 bakkies van 32768B reeks
2 bakkies van 262144B reeks
1 bak vir oorblywende groottes
Groot bak groottes kode
```c // From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
2 groot toekenning word uitgevoer, dan een word vrygestel (wat dit in die ongesorteerde houer plaas) en 'n groter toekenning word gemaak (wat die vry een van die ongesorteerde houer na die groot houer skuif).
Kompileer dit en ontleed dit met 'n breekpunt in die ret opcode van die main funksie. dan met gef kan jy sien dat die tcache houer vol is en een brokkie in die groot houer is:
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.
Boonste Brok
// 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))
Hierdie is basies 'n blok wat al die tans beskikbare heap bevat. Wanneer 'n malloc uitgevoer word, as daar nie 'n beskikbare vry blok is om te gebruik nie, sal hierdie boonste blok sy grootte verminder om die nodige spasie te gee. Die aanwyser na die Boonste Blok word gestoor in die malloc_state struktuur.
Verder, aan die begin, is dit moontlik om die ongesorteerde blok as die boonste blok te gebruik.
Waarnemings van die Boonste Blok voorbeeld
```c #include #include
int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); return 0; }
Na die samestelling en foutopsporing daarvan met 'n breekpunt in die `ret` opcode van `main` het ek gesien dat die malloc die adres `0xaaaaaaac12a0` teruggegee het en dit is die stukke:
```bash
gef➤ heap chunks
Chunk(addr=0xaaaaaaac1010, size=0x290, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac1010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................]
Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12a0 41 41 41 41 41 41 41 00 00 00 00 00 00 00 00 00 AAAAAAA.........]
Chunk(addr=0xaaaaaaac12c0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac12c0 41 64 64 72 65 73 73 20 6f 66 20 74 68 65 20 63 Address of the c]
Chunk(addr=0xaaaaaaac16d0, size=0x410, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
[0x0000aaaaaaac16d0 41 41 41 41 41 41 41 0a 00 00 00 00 00 00 00 00 AAAAAAA.........]
Chunk(addr=0xaaaaaaac1ae0, size=0x20530, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA) ← top chunk
Waar dit gesien kan word dat die boonste blok by adres 0xaaaaaaac1ae0 is. Dit is geen verrassing nie omdat die laaste toegewysde blok was by 0xaaaaaaac12a0 met 'n grootte van 0x410 en 0xaaaaaaac12a0 + 0x410 = 0xaaaaaaac1ae0.
Dit is ook moontlik om die lengte van die Boonste blok op sy blokkop te sien:
Wanneer malloc gebruik word en 'n stuk verdeel word (van die ongesorteerde bin of van die boonste stuk byvoorbeeld), word die stuk wat geskep word uit die res van die verdeelde stuk Laaste Restant genoem en sy aanwysers word gestoor in die malloc_state struktuur.
