Heap

Misingi ya Heap

Heap ni mahali ambapo programu itaweza kuhifadhi data wakati inahitaji data kwa kuita kazi kama vile malloc, calloc... Zaidi ya hayo, wakati kumbukumbu hii haifai tena, inapatikana kwa kuita kazi free.

Kama inavyoonekana, iko baada ya ambapo binary inapakiwa kwenye kumbukumbu (angalia sehemu ya [heap]):

Ugawaji wa Kipande Msingi

Wakati data fulani inahitajika kuhifadhiwa kwenye heap, sehemu ya heap inatengwa kwa hilo. Sehemu hii itakuwa ya benki na tu data iliyohitajika + nafasi ya vichwa vya benki + kisawe cha ukubwa wa benki kitahifadhiwa kwa kipande. lengo ni kuweka kumbukumbu kiasi cha chini iwezekanavyo bila kufanya iwe ngumu kujua wapi kila kipande kipo. Kwa hili, habari ya kipande cha metadata hutumiwa kujua wapi kila kipande kilichotumiwa/kilichofunguliwa kipo.

Kuna njia tofauti za kutenga nafasi hasa ikitegemea benki iliyotumiwa, lakini njia ya jumla ni kama ifuatavyo:

Programu inaanza kwa kuomba kiasi fulani cha kumbukumbu.
Ikiwa kwenye orodha ya vipande kuna mtu anayeweza kutosha kufikia ombi, itatumika
Hii inaweza hata maanisha sehemu ya kipande kinachopatikana kitatumika kwa ombi hili na sehemu iliyobaki itaongezwa kwenye orodha ya vipande
Ikiwa hakuna kipande kinachopatikana kwenye orodha lakini bado kuna nafasi katika kumbukumbu iliyotengwa, meneja wa heap huanzisha kipande kipya
Ikiwa hakuna nafasi ya kutosha ya kumbukumbu ya heap kutenga kipande kipya, meneja wa heap huomba kernel kupanua kumbukumbu iliyotengwa kwa heap na kisha kutumia kumbukumbu hii kuzalisha kipande kipya
Ikiwa kila kitu kinafeli, malloc inarudisha null.

Tambua kwamba ikiwa kumbukumbu iliyohitajika inapita kizingiti, mmap itatumika kutambaza kumbukumbu iliyohitajika.

Maeneo

Katika maombi ya multithreaded, meneja wa heap lazima azuie hali za mbio ambazo zinaweza kusababisha ajali. Awali, hii ilifanywa kwa kutumia mutex ya ulimwengu kuhakikisha kwamba tu mnyororo mmoja unaweza kupata heap kwa wakati mmoja, lakini hii ilisababisha matatizo ya utendaji kutokana na kizuizi kilichosababishwa na mutex.

Kushughulikia hili, mpangilio wa heap wa ptmalloc2 uliingiza "arenas," ambapo kila uwanja unafanya kazi kama heap tofauti na miundo yake ya data yenyewe na mutex, kuruhusu mnyororo wa multiple kufanya shughuli za heap bila kuingiliana, ikiwa wanatumia uwanja tofauti.

Uwanja "kuu" wa msingi unashughulikia shughuli za heap kwa maombi ya mnyororo mmoja. Wakati mnyororo mpya unapoongezwa, meneja wa heap huwapa arenas za pili kupunguza mzozo. Kwanza inajaribu kuambatanisha kila mnyororo mpya kwenye uwanja usiotumiwa, ukiunda mpya ikihitajika, hadi kufikia kikomo cha mara 2 ya viwango vya CPU kwa mifumo ya 32-bit na mara 8 kwa mifumo ya 64-bit. Mara kikomo kinapofikiwa, mnyororo lazima washiriki arenas, ikiongoza kwa mzozo wa uwezekano.

Tofauti na uwanja wa msingi, ambao unapanuka kwa kutumia wito wa mfumo wa brk, arenas za pili hujenga "subheaps" kwa kutumia mmap na mprotect kusimuliza tabia ya heap, kuruhusu mabadiliko katika kusimamia kumbukumbu kwa shughuli za multithreaded.

Subheaps

Subheaps hutumika kama akiba ya kumbukumbu kwa arenas za pili katika maombi ya multithreaded, kuruhusu kuzidi na kusimamia maeneo yao ya heap kando na heap kuu. Hapa kuna jinsi subheaps zinavyotofautiana na heap ya awali na jinsi wanavyofanya kazi:

Heap ya Awali vs. Subheaps:

Heap ya awali iko moja kwa moja baada ya binary ya programu kwenye kumbukumbu, na inapanuka kwa kutumia wito wa mfumo wa sbrk.
Subheaps, zinazotumiwa na arenas za pili, hujengwa kupitia mmap, wito wa mfumo unaotambaza eneo maalum la kumbukumbu.

Akiba ya Kumbukumbu na mmap:

Meneja wa heap anapounda subheap, inahifadhi kipande kikubwa cha kumbukumbu kupitia mmap. Akiba hii haialoishi kumbukumbu mara moja; inatambulisha tu eneo ambalo michakato au alokesheni zingine hazipaswi kutumia.
Kwa chaguo-msingi, ukubwa uliohifadhiwa kwa subheap ni 1 MB kwa mchakato wa 32-bit na 64 MB kwa mchakato wa 64-bit.

Upanuzi wa Hatua kwa Hatua na mprotect:

Eneo la kumbukumbu lililohifadhiwa awali linawekwa alama kama PROT_NONE, ikionyesha kuwa kernel haitaji kutenga kumbukumbu ya kimwili kwa nafasi hii bado.
Ili "kukuza" subheap, meneja wa heap hutumia mprotect kubadilisha ruhusa za ukurasa kutoka PROT_NONE hadi PROT_READ | PROT_WRITE, ikichochea kernel kutenga kumbukumbu ya kimwili kwa anwani zilizohifadhiwa hapo awali. Hatua hii kwa hatua inaruhusu subheap kupanuka kama inavyohitajika.
Mara subheap nzima inapomalizika, meneja wa heap huunda subheap mpya kuendelea kutenga.

Metadata

Kama ilivyotajwa hapo awali, vipande hivi pia vina metadata fulani, iliyowakilishwa vizuri sana kwenye picha hii:

Kawaida metadata ni 0x08B ikionyesha ukubwa wa sasa wa kipande kwa kutumia biti za mwisho 3 kumaanisha:

A: Ikiwa ni 1 inatoka kwa subheap, ikiwa ni 0 iko kwenye uwanja mkuu
M: Ikiwa ni 1, kipande hiki ni sehemu ya nafasi iliyotengwa na mmap na sio sehemu ya heap
P: Ikiwa ni 1, kipande kilichotangulia kinafanya kazi

Kisha, nafasi kwa data ya mtumiaji, na mwishowe 0x08B kuonyesha ukubwa wa kipande kilichotangulia wakati kipande kinapatikana (au kuhifadhi data ya mtumiaji wakati inatengwa).

Zaidi, inapopatikana, data ya mtumiaji hutumiwa kuhifadhi pia baadhi ya data:

Kiashiria kwa kipande kifuatacho
Kiashiria kwa kipande kilichotangulia
Ukubwa wa kipande kifuatacho kwenye orodha
Ukubwa wa kipande kilichotangulia kwenye orodha

Tambua jinsi kufanana na orodha hii njia hii inazuia haja ya kuwa na safu ambapo kila kipande kimoja kinarekodiwa.

Ulinzi wa Kufuta

Ili kulinda kutokana na matumizi ya bahati mbaya au yaliyokusudiwa ya kazi ya bure, kabla ya kutekeleza vitendo vyake hufanya ukaguzi fulani:

Inakagua kwamba anwani imepangiliwa kwenye mpaka wa byte 8 au 16 kwenye mpaka wa 64-bit ((anwani % 16) == 0), tangu malloc inahakikisha kuwa alokesheni zote zimepangiliwa.
Inakagua kwamba uga wa ukubwa wa kipande hauwezi kuwa wa kidogo sana, mkubwa sana, si ukubwa uliopangiliwa, au ungekumbana na mwisho wa nafasi ya anwani ya mchakato.
Inakagua kwamba kipande kipo ndani ya mipaka ya uwanja.
Inakagua kwamba kipande hajatajwa kama huru tayari kwa kuangalia biti "P" inayopatikana kwenye metadata mwanzoni mwa kipande kifuatacho.

Bins

Ili kuboresha ufanisi wa jinsi vipande vinavyohifadhiwa, kila kipande sio tu katika orodha moja iliyounganishwa, lakini kuna aina kadhaa. Hizi ni mabano na kuna aina 5 za mabano: 62 mabano madogo, 63 mabano makubwa, 1 mabano yasiyopangwa, 10 mabano ya haraka na 64 mabano ya tcache kwa kila mnyororo.

Anwani ya awali ya kila mabano yasiyopangwa, madogo na makubwa iko ndani ya safu moja. Indeksi 0 haifai, 1 ni mabano yasiyopangwa, mabano 2-64 ni mabano madogo na mabano 65-127 ni mabano makubwa.

Mabano Madogo

Mabano madogo ni haraka kuliko mabano makubwa lakini polepole kuliko mabano ya haraka.

Kila bano la 62 litakuwa na vipande vya saizi ile ile: 16, 24, ... (ikiwa na saizi ya juu ya 504 baiti katika bits 32 na 1024 katika bits 64). Hii husaidia katika kasi ya kupata bano ambapo nafasi inapaswa kutengwa na kuingiza na kuondoa viingilio kwenye orodha hizi.

Mabano Makubwa

Tofauti na mabano madogo, ambayo yanashughulikia vipande vya saizi iliyowekwa, kila bano kubwa hushughulikia safu ya vipande vya saizi. Hii ni ya kubadilika zaidi, kuruhusu mfumo kuhimili saizi tofauti bila kuhitaji bano tofauti kwa kila saizi.

Katika mpangilio wa kumbukumbu, mabano makubwa huanza pale mabano madogo yanapoishia. Safu za mabano makubwa hukua kwa ukubwa unaokua, maana bano la kwanza linaweza kufunika vipande kutoka 512 hadi 576 baiti, wakati inayofuata inafunika kutoka 576 hadi 640 baiti. Mtindo huu unaendelea, na bano kubwa zaidi linalojumuisha vipande vyote zaidi ya 1MB.

Mabano makubwa ni polepole kufanya kazi ikilinganishwa na mabano madogo kwa sababu wanapaswa kupanga na kutafuta kupitia orodha ya vipande vya saizi tofauti ili kupata saizi bora kwa kutengwa. Wakati kipande kinapowekwa kwenye bano kubwa, lazima kipangwe, na wakati kumbukumbu inatengwa, mfumo lazima upate kipande sahihi. Kazi hii ya ziada inawafanya kuwa polepole, lakini kwa kuwa kutengwa kwa vipande vikubwa ni nadra kuliko vile vidogo, ni sawa kufanya biashara hiyo.

Kuna:

Mabano 32 ya safu ya 64B
Mabano 16 ya safu ya 512B
Mabano 8 ya safu ya 4096B
Mabano 4 ya safu ya 32768B
Mabano 2 ya safu ya 262144B
Mabano 1 ya kwa saizi zilizosalia

Bano Lisilopangwa

Bano lisilopangwa ni hifadhi ya haraka inayotumiwa na meneja wa kumbukumbu ili kufanya kutengwa kwa kumbukumbu kuwa haraka. Hivi ndivyo inavyofanya kazi: Wakati programu inaachilia kumbukumbu, meneja wa kumbukumbu haitoi mara moja kwenye bano maalum. Badala yake, kwanza inajaribu kulijumuisha na vipande vya bure vya jirani ili kuunda kibodi kubwa ya kumbukumbu ya bure. Kisha, inaweka kipande kipya hiki kwenye bano la jumla linaloitwa "bano lisilopangwa."

Wakati programu inapoomba kumbukumbu, meneja wa kumbukumbu kwanza huchunguza bano lisilopangwa kuona ikiwa kuna kipande cha saizi sahihi. Ikiipata, inaitumia mara moja, ambayo ni haraka kuliko kutafuta kupitia mabano mengine. Ikiwa haina kipande kinachofaa, inahamisha vipande vilivyofutwa kwenye mabano yao sahihi, iwe madogo au makubwa, kulingana na saizi zao.

Kwa hivyo, bano lisilopangwa ni njia ya kuharakisha kutengwa kwa kumbukumbu kwa haraka kwa kutumia tena kumbukumbu iliyofutwa hivi karibuni na kupunguza haja ya kutafuta na kujumuisha kwa muda mrefu.

Tafadhali kumbuka kwamba hata kama vipande ni vya makundi tofauti, mara kwa mara, ikiwa kipande kinapatikana kinaingiliana na kipande kingine kilichopo (hata kama ni vikundi tofauti), vitajumuishwa.

Mabano ya Haraka

Mabano ya haraka yameundwa kwa lengo la kufanya kutengwa kwa kumbukumbu kwa vipande vidogo kuwa haraka kwa kuweka vipande vilivyofutwa hivi karibuni katika muundo wa kupata haraka. Mabano haya hutumia njia ya Mwisho-Kuingia, Kwanza-Kutoka (LIFO), maana kwamba kipande kilichofutwa hivi karibuni ndicho kwanza kutumika wakati kuna ombi jipya la kutengwa. Tabia hii ni faida kwa kasi, kwani ni haraka kuingiza na kuondoa kutoka juu ya rundo (LIFO) ikilinganishwa na foleni (FIFO).

Aidha, mabano ya haraka hutumia orodha za kushikamana moja, sio mbili, ambayo inaboresha kasi zaidi. Kwa kuwa vipande katika mabano ya haraka havijajumuishwa na majirani, hakuna haja ya muundo tata unaoruhusu kuondolewa katikati. Orodha ya kushikamana moja ni rahisi na haraka kwa shughuli hizi.

Kimsingi, kinachotokea hapa ni kwamba kichwa (kiashiria cha kipande cha kwanza cha kuangalia) kinaelekeza daima kwenye kipande kilichofutwa hivi karibuni cha saizi hiyo. Kwa hivyo:

Wakati kipande kipya kinatengwa cha saizi hiyo, kichwa kinaelekeza kwenye kipande cha bure cha kutumia. Kwa kuwa kipande hiki cha bure kinaelekeza kwa kile kinachofuata kutumika, anwani hii inahifadhiwa kwenye kichwa ili kutambua wapi kupata kipande kinachopatikana
Wakati kipande kinapofutwa, kipande cha bure kitahifadhi anwani ya kipande kinachopatikana kwa sasa na anwani ya kipande hiki kilichofutwa hivi karibuni itawekwa kwenye kichwa

Vipande katika mabano ya haraka havijawekwa moja kwa moja kama vipande vilivyopo hivyo vinabaki kama vipande vya mabano ya haraka kwa muda fulani badala ya kuweza kujumuishwa na vipande vingine.

Mabano ya Tcache (Hifadhi kwa Mnyororo)

Ingawa mnyororo unajaribu kuwa na kumbukumbu yake mwenyewe (angalia Arenas na Subheaps), kuna uwezekano kwamba mchakato na idadi kubwa ya mnyororo (kama seva ya wavuti) itamaliza kushiriki kumbukumbu na mnyororo mwingine. Katika kesi hii, suluhisho kuu ni matumizi ya kifungio, ambacho kinaweza kupunguza kwa kiasi kikubwa kasi ya mnyororo.

Kwa hivyo, tcache ni sawa na bano la haraka kwa kila mnyororo kwa njia kwamba ni orodha ya kushikamana moja ambayo haifanyi vipande. Kila mnyororo ana mabano 64 ya tcache ya kushikamana moja. Kila bano linaweza kuwa na kiwango cha juu cha vipande 7 vya saizi ile ile kutoka 24 hadi 1032B kwenye mifumo ya 64-bit na 12 hadi 516B kwenye mifumo ya 32-bit.

Wakati mnyororo anapofuta kipande, ikiwa sio kikubwa sana kwa kutengwa kwenye tcache na bano la tcache halijajaa (tayari vipande 7), itawekwa hapo. Ikiwa haitaweza kwenda kwenye tcache, italazimika kusubiri kwa kifungio cha kumbukumbu ili kuweza kufanya operesheni ya kutolewa kwa jumla.

Wakati kipande kinapotengwa, ikiwa kuna kipande cha bure cha saizi inayohitajika kwenye Tcache itakitumia, ikiwa la, italazimika kusubiri kifungio cha kumbukumbu ili kuweza kupata moja kwenye mabano ya jumla au kuunda mpya. Pia kuna uboreshaji, katika kesi hii, wakati wa kuwa na kifungio cha kumbukumbu, mnyororo atajaza Tcache yake na vipande vya kumbukumbu (7) vya saizi inayohitajika, hivyo ikihitaji zaidi, itavipata kwenye Tcache.

Mpangilio wa Bins

Kwa kutenga:

Ikiwa kuna kipande kinachopatikana kwenye Tcache ya saizi hiyo, tumia Tcache
Ikiwa ni kubwa sana, tumia mmap
Pata kizuizi cha dimbwi la uwanja na:
Ikiwa saizi ya kutosha ndogo, kipande cha dimbwi la haraka kinapatikana kwa saizi iliyohitajika, kitumie na jaza tcache kutoka kwa dimbwi la haraka
Angalia kila kuingia kwenye orodha isiyopangwa ikisaka kipande kikubwa cha kutosha, na jaza tcache ikiwezekana
Angalia mabakuli madogo au makubwa (kulingana na saizi iliyohitajika) na jaza tcache ikiwezekana
Unda kipande kipya kutoka kwa kumbukumbu inayopatikana
Ikiwa hakuna kumbukumbu inayopatikana, pata zaidi kwa kutumia sbrk
Ikiwa kumbukumbu kuu ya dimbwi haiwezi kuongezeka zaidi, unda nafasi mpya kwa kutumia mmap
Ikiwa hakuna kilichofanya kazi, rudisha thamani tupu

Kwa kufuta:

Ikiwa kidude ni Null, maliza
Fanya ukaguzi wa akili wa free kwenye kipande kujaribu kuthibitisha ni kipande halali
Ikiwa ni ndogo vya kutosha na tcache haijajaa, weka hapo
Ikiwa biti M imewekwa (si dimbwi), tumia munmap
Pata kizuizi cha dimbwi la uwanja:
Ikiwa inalingana na fastbin, weka hapo
Ikiwa kipande ni > 64KB, unganisha fastbins mara moja na weka vipande vilivyoundwa kwenye dimbwi lisilopangwa.
Unganisha kipande nyuma na mbele na vipande vilivyofutwa jirani katika mabakuli madogo, makubwa, na yasiyopangwa ikiwa kuna
Ikiwa kwenye kichwa, unganisha kwenye kumbukumbu isiyoitumiwa
Ikiwa sio vingine vilivyotangulia, ihifadhi kwenye orodha isiyopangwa

Mfano wa haraka wa dimbwi kutoka https://guyinatuxedo.github.io/25-heap/index.html lakini kwa arm64:

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

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

Wekeza kizuizi mwishoni mwa kazi kuu na tujue mahali data ilihifadhiwa:

Inawezekana kuona kwamba herufi panda ilihifadhiwa kwa 0xaaaaaaac12a0 (ambayo ilikuwa anwani iliyotolewa kama jibu na malloc ndani ya x0). Kwa kuangalia 0x10 baits kabla yake, inawezekana kuona kwamba 0x0 inawakilisha kwamba kitengo cha awali hakijatumika (urefu 0) na kwamba urefu wa kitengo hiki ni 0x21.

Nafasi za ziada zilizohifadhiwa (0x21-0x10=0x11) zinatoka kwa vichwa vilivyozidishwa (0x10) na 0x1 haimaanishi kwamba ilihifadhiwa 0x21B lakini biti za mwisho 3 za urefu wa kichwa cha sasa zina maana maalum. Kwa kuwa urefu daima ni kielelezo cha 16-baiti (kwenye mashine za 64bits), biti hizi hazitatumika kamwe na nambari ya urefu.

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

Marejeo

PreviousFormat Strings Template NextUse After Free

Last updated 1 hour ago