Hoe werken malloc() en free()?

Ik wil weten hoe mallocen freewerken.

int main() {
    unsigned char *p = (unsigned char*)malloc(4*sizeof(unsigned char));
    memset(p,0,4);
    strcpy((char*)p,"abcdabcd"); // **deliberately storing 8bytes**
    cout << p;
    free(p); // Obvious Crash, but I need how it works and why crash.
    cout << p;
    return 0;
}

Ik zou erg dankbaar zijn als het antwoord diepgaand is op geheugenniveau, als dat mogelijk is.

Antwoord 1, autoriteit 100%

Ok, er zijn al antwoorden over malloc gepost.

Het interessantere is hoe gratis werkt(en in deze richting kan ook malloc beter worden begrepen).

In veel malloc/free-implementaties retourneert gratis het geheugen normaal gesproken niet naar het besturingssysteem (of in ieder geval slechts in zeldzame gevallen). De reden is dat je gaten in je heap krijgt en dus kan het gebeuren dat je je 2 of 4 GB virtueel geheugen gewoon opvult met gaten. Dit moet worden vermeden, want zodra het virtuele geheugen op is, komt u in grote problemen. De andere reden is dat het besturingssysteem alleen geheugenbrokken aankan die een specifieke grootte en uitlijning hebben. Om specifiek te zijn: normaal gesproken kan het besturingssysteem alleen blokken aan die de virtuele geheugenbeheerder aankan (meestal veelvouden van 512 bytes, bijvoorbeeld 4 KB).

Dus 40 bytes terugsturen naar het besturingssysteem werkt gewoon niet. Dus wat doet gratis?

Free zal het geheugenblok in zijn eigen lijst met vrije blokken plaatsen. Normaal gesproken probeert het ook aangrenzende blokken in de adresruimte samen te voegen. De gratis blokkeringslijst is slechts een cirkelvormige lijst van geheugenbrokken die in het begin wat administratieve gegevens bevatten. Dit is ook de reden waarom het beheren van zeer kleine geheugenelementen met de standaard malloc/free niet efficiënt is. Elke geheugenbrok heeft extra data nodig en bij kleinere formaten vindt meer fragmentatie plaats.

De gratis lijst is ook de eerste plaats waar malloc naar kijkt als er een nieuw stuk geheugen nodig is. Het wordt gescand voordat het nieuw geheugen van het besturingssysteem vraagt. Wanneer een brok wordt gevonden dat groter is dan het benodigde geheugen, wordt het in twee delen verdeeld. De ene wordt teruggestuurd naar de beller, de andere wordt teruggezet in de gratis lijst.

Er zijn veel verschillende optimalisaties voor dit standaardgedrag (bijvoorbeeld voor kleine stukjes geheugen). Maar aangezien malloc en gratis zo universeel moeten zijn, is het standaardgedrag altijd de uitwijkmogelijkheid wanneer alternatieven niet bruikbaar zijn. Er zijn ook optimalisaties in het omgaan met de vrije lijst – bijvoorbeeld het opslaan van de chunks in lijsten gesorteerd op grootte. Maar alle optimalisaties hebben ook hun eigen beperkingen.

Waarom crasht je code:

De reden is dat door 9 tekens te schrijven (vergeet de achterste null-byte niet) in een gebied van 4 tekens, u waarschijnlijk de administratieve gegevens overschrijft die zijn opgeslagen voor een ander stuk geheugen dat zich “achter” uw stuk bevindt van gegevens (aangezien deze gegevens meestal “voor” de geheugenbrokken worden opgeslagen). Wanneer free vervolgens probeert uw chunk in de gratis lijst te plaatsen, kan het deze administratieve gegevens raken en daardoor struikelen over een overschreven pointer. Dit zal het systeem laten crashen.

Dit is nogal gracieus gedrag. Ik heb ook situaties gezien waarin een weggelopen aanwijzer ergens gegevens in de geheugenvrije lijst heeft overschreven en het systeem niet onmiddellijk crashte, maar enkele subroutines later. Zelfs in een systeem van gemiddelde complexiteit kunnen dergelijke problemen heel, heel moeilijk te debuggen zijn! In het ene geval waarbij ik betrokken was, kostte het ons (een grotere groep ontwikkelaars) enkele dagen om de reden van de crash te vinden — aangezien het zich op een totaal andere locatie bevond dan die aangegeven door de geheugendump. Het is als een tijdbom. Weet je, je volgende “gratis” of “malloc” zal crashen, maar je weet niet waarom!

Dit zijn enkele van de ergste C/C++-problemen en een van de redenen waarom pointers zo problematisch kunnen zijn.

Antwoord 2, autoriteit 14%

Zoals aluser zegt in deze forumthread:

Uw proces heeft een geheugengebied, van adres x tot adres y,
riep de hoop. Al uw malloc’d-gegevens bevinden zich in dit gebied. mallok()
houdt een gegevensstructuur bij, laten we zeggen een lijst, van alle gratis stukjes van
ruimte in de hoop. Als je malloc belt, zoekt hij in de lijst naar:
een stuk dat groot genoeg is voor jou, geeft er een verwijzing naar terug, en
registreert het feit dat het niet meer gratis is en hoe groot het is.
Als je free() aanroept met dezelfde aanwijzer, zoekt free() op hoe groot
dat chunk is en voegt het weer toe aan de lijst met gratis chunks(). als jij
bel malloc() en het kan geen groot genoeg stuk in de heap vinden, het
gebruikt de brk() syscall om de heap te laten groeien, d.w.z. verhoog adres y en
ervoor zorgen dat alle adressen tussen de oude y en de nieuwe y geldig zijn
geheugen. brk() moet een syscall zijn; er is geen manier om hetzelfde te doen
volledig vanuit gebruikersruimte.

malloc() is systeem-/compilerafhankelijk, dus het is moeilijk om een specifiek antwoord te geven. In principe houdt het echter wel bij welk geheugen het is toegewezen en afhankelijk van hoe het dat doet, kunnen uw oproepen naar gratis mislukken of slagen.

malloc() and free() don't work the same way on every O/S.

Antwoord 3, autoriteit 10%

Eén implementatie van malloc/free doet het volgende:

1. Verkrijg een geheugenblok van het besturingssysteem via sbrk() (Unix-aanroep).
2. Maak een kop- en voettekst rond dat geheugenblok met wat informatie zoals grootte, rechten en waar het volgende en vorige blok zich bevinden.
3. Als een oproep naar malloc binnenkomt, wordt er verwezen naar een lijst die verwijst naar blokken van de juiste grootte.
4. Dit blok wordt dan geretourneerd en kop- en voetteksten worden dienovereenkomstig bijgewerkt.

Antwoord 4, autoriteit 7%

Geheugenbeveiliging heeft pagina-granulariteit en vereist kernelinteractie

Je voorbeeldcode vraagt in wezen waarom het voorbeeldprogramma niet trapt, en het antwoord is dat geheugenbescherming een kernelfunctie is en alleen van toepassing is op hele pagina’s, terwijl de geheugentoewijzer een bibliotheekfunctie is en het beheert .. zonder handhaving .. blokken van willekeurige grootte die vaak veel kleiner zijn dan pagina’s.

Geheugen kan alleen in eenheden van pagina’s uit uw programma worden verwijderd, en zelfs dat is onwaarschijnlijk.

calloc(3) en malloc(3) werken samen met de kernel om geheugen te krijgen, indien nodig. Maar de meeste implementaties van free(3) geven geen geheugen terug aan de kernel¹, ze voegen het gewoon toe aan een vrije lijst die calloc() en malloc() later zullen raadplegen om de vrijgegeven blokken opnieuw te gebruiken .

Zelfs als een free() geheugen zou willen teruggeven aan het systeem, zou het ten minste één aaneengesloten geheugenpagina nodig hebben om de kernel de regio daadwerkelijk te laten beschermen, dus het vrijgeven van een klein blok zou alleen leiden tot een wijziging van de bescherming als het het laatstekleine blok op een pagina was.

Dus je blok is daar, zittend op de gratis lijst. Je hebt bijna altijd toegang tot het en het nabijgelegen geheugen, net alsof het nog steeds is toegewezen. C compileert rechtstreeks naar machinecode en zonder speciale debugging-arrangementen zijn er geen sanity-checks op ladingen en winkels. Als u nu probeert toegang te krijgen tot een gratis blok, wordt het gedrag niet gedefinieerd door de standaard om geen onredelijke eisen te stellen aan bibliotheekimplementators. Als je probeert toegang te krijgen tot vrijgemaakt geheugen of geheugen buiten een toegewezen blok, zijn er verschillende dingen die fout kunnen gaan:

• Soms houden toewijzers afzonderlijke geheugenblokken bij, soms gebruiken ze een koptekst die ze net voor of na (een “voettekst”, denk ik) je blok toewijzen, maar ze willen misschien gewoon geheugen binnen het blok gebruiken om de gratis lijst aan elkaar gekoppeld. Als dit het geval is, is het lezen van het blok in orde, maar de inhoud kan veranderen, en het schrijven naar het blok kan ertoe leiden dat de allocator zich misdraagt of crasht.
• Natuurlijk kan je blok in de toekomst worden toegewezen, en dan wordt het waarschijnlijk overschreven door je code of een bibliotheekroutine, of met nullen door calloc().
• Als het blok opnieuw wordt toegewezen, kan de grootte ervan ook worden gewijzigd, in welk geval er op verschillende plaatsen nog meer links of initialisatie zullen worden geschreven.
• Het is duidelijk dat je zo ver buiten bereik kunt verwijzen dat je een grens van een van de kernel-bekende segmenten van je programma overschrijdt, en in dit ene geval zul je vallen.

Theorie van de werking

Dus, terugwerkend van je voorbeeld naar de algemene theorie, malloc(3) haalt geheugen uit de kernel wanneer het het nodig heeft, en meestal in eenheden van pagina’s. Deze pagina’s zijn opgedeeld of samengevoegd zoals het programma vereist. Malloc en Free werken samen om een directory bij te houden. Ze voegen, indien mogelijk, aangrenzende vrije blokken samen om grote blokken te kunnen leveren. De directory kan al dan niet inhouden dat het geheugen in vrijgemaakte blokken wordt gebruikt om een gekoppelde lijst te vormen. (Het alternatief is een beetje meer gedeeld geheugen en paging-vriendelijk, en het omvat het toewijzen van geheugen specifiek voor de map.) Malloc en gratis hebben weinig of geen mogelijkheid om toegang tot individuele blokken af te dwingen, zelfs wanneer speciale en optionele foutopsporingscode is gecompileerd in het programma.

^{1. Het feit dat maar heel weinig implementaties van free() proberen geheugen terug te geven aan het systeem, is niet noodzakelijk te wijten aan het feit dat de implementatieprogramma’s verslappen. Interactie met de kernel is veel langzamer dan alleen het uitvoeren van bibliotheekcode, en het voordeel zou klein zijn. De meeste programma’s hebben een stabiele of toenemende geheugenvoetafdruk, dus de tijd die wordt besteed aan het analyseren van de heap op zoek naar herbruikbaar geheugen zou volledig verspild zijn. Andere redenen zijn onder meer het feit dat interne fragmentatie het onwaarschijnlijk maakt dat pagina-uitgelijnde blokken bestaan, en het is waarschijnlijk dat het retourneren van een blok blokken naar beide kanten zou fragmenteren. Ten slotte, de weinige programma’s die grote hoeveelheden geheugen teruggeven, zullen waarschijnlijk malloc() omzeilen en toch gewoon pagina’s toewijzen en vrijmaken.}

Antwoord 5, autoriteit 6%

In theorie haalt malloc geheugen uit het besturingssysteem voor deze applicatie. Omdat je misschien maar 4 bytes wilt en het besturingssysteem in pagina’s moet werken (vaak 4k), doet malloc iets meer dan dat. Het neemt een pagina in beslag en plaatst zijn eigen informatie daarin, zodat het kan bijhouden wat je hebt toegewezen en vrijgemaakt van die pagina.

Als je bijvoorbeeld 4 bytes toewijst, geeft malloc je een pointer naar 4 bytes. Wat je je misschien niet realiseert, is dat het geheugen van 8-12 bytes vóórje 4 bytes door malloc wordt gebruikt om een ketting te maken van al het geheugen dat je hebt toegewezen. Wanneer u gratis belt, neemt het uw aanwijzer, maakt een back-up naar waar de gegevens zich bevinden en werkt daarop.

Als je geheugen vrijmaakt, haalt malloc dat geheugenblok uit de keten… en kan dat geheugen al dan niet teruggeven aan het besturingssysteem. Als dit het geval is, zal de toegang tot dat geheugen waarschijnlijk mislukken, omdat het besturingssysteem uw machtigingen voor toegang tot die locatie zal afnemen. Als malloc het geheugen behoudt (omdat er andere dingen aan die pagina zijn toegewezen, of voor een of andere optimalisatie), dan zal de toegang werken. Het is nog steeds fout, maar het zou kunnen werken.

DISCLAIMER: Wat ik beschreef is een algemene implementatie van malloc, maar zeker niet de enige mogelijke.

Antwoord 6, autoriteit 3%

Je strcpy-regel probeert 9 bytes op te slaan, niet 8, vanwege de NUL-terminator. Het roept ongedefinieerd gedrag op.

De oproep naar gratis kan wel of niet crashen. Het geheugen “na” de 4 bytes van uw toewijzing kan door uw C- of C++-implementatie voor iets anders worden gebruikt. Als het voor iets anders wordt gebruikt, dan zal het overal over heen krabbelen ervoor zorgen dat “iets anders” fout gaat, maar als het niet voor iets anders wordt gebruikt, zou je er toevallig mee weg kunnen komen. “Er mee wegkomen” klinkt misschien goed, maar is eigenlijk slecht, omdat het betekent dat je code goed lijkt te werken, maar in de toekomst kom je er misschien niet mee weg.

Met een geheugentoewijzer in debugging-stijl, zou je kunnen ontdekken dat daar een speciale bewakingswaarde is geschreven, en die gratis controleert op die waarde en in paniek raakt als hij deze niet vindt.

Anders zou je kunnen ontdekken dat de volgende 5 bytes een deel van een verbindingsknooppunt bevatten dat bij een ander geheugenblok hoort dat nog niet is toegewezen. Het vrijmaken van je blok zou kunnen betekenen dat je het toevoegt aan een lijst met beschikbare blokken, en omdat je in het lijstknooppunt hebt gekrabbeld, kan die bewerking een verwijzing naar een aanwijzer met een ongeldige waarde verwijderen, wat een crash veroorzaakt.

Het hangt allemaal af van de geheugentoewijzer – verschillende implementaties gebruiken verschillende mechanismen.

Antwoord 7, autoriteit 3%

Hoe malloc() en free() werken, hangt af van de gebruikte runtime-bibliotheek. In het algemeen wijst malloc() een heap (een blok geheugen) toe aan het besturingssysteem. Elk verzoek aan malloc() wijst vervolgens een klein deel van dit geheugen toe en retourneert een aanwijzer naar de aanroeper. De geheugentoewijzingsroutines zullen wat extra informatie over het toegewezen geheugenblok moeten opslaan om gebruikt en vrij geheugen op de heap te kunnen bijhouden. Deze informatie wordt vaak opgeslagen in een paar bytes net voor de aanwijzer die wordt geretourneerd door malloc() en het kan een gekoppelde lijst met geheugenblokken zijn.

Door voorbij het geheugenblok te schrijven dat door malloc() is toegewezen, vernietigt u hoogstwaarschijnlijk een deel van de boekhoudinformatie van het volgende blok, dat het resterende ongebruikte geheugenblok kan zijn.

Een plaats waar uw programma ook kan crashen, is wanneer u te veel tekens naar de buffer kopieert. Als de extra tekens zich buiten de heap bevinden, kunt u een toegangsfout krijgen als u naar niet-bestaand geheugen probeert te schrijven.

Antwoord 8

Dit heeft niets specifieks te maken met malloc en free. Je programma vertoont ongedefinieerd gedrag nadat je de string hebt gekopieerd – het kan op dat moment of op enig moment daarna crashen. Dit zou zelfs waar zijn als je nooit malloc en free hebt gebruikt en de char-array op de stapel of statisch hebt toegewezen.

Antwoord 9

malloc en free zijn implementatie-afhankelijk. Een typische implementatie omvat het partitioneren van beschikbaar geheugen in een “vrije lijst” – een gekoppelde lijst met beschikbare geheugenblokken. Veel implementaties verdelen het kunstmatig in kleine versus grote objecten. Vrije blokken beginnen met informatie over hoe groot het geheugenblok is en waar het volgende is, enz.

Als je malloc gebruikt, wordt er een blok uit de vrije lijst gehaald. Wanneer je vrijmaakt, wordt het blok teruggezet in de vrije lijst. De kans is groot dat wanneer u het einde van uw aanwijzer overschrijft, u op de kop van een blok in de vrije lijst schrijft. Wanneer je je geheugen vrijmaakt, probeert free() naar het volgende blok te kijken en zal waarschijnlijk een aanwijzer raken die een busfout veroorzaakt.

Antwoord 10

Nou, het hangt af van de implementatie van de geheugentoewijzer en het besturingssysteem.

Onder Windows kan een proces bijvoorbeeld om een pagina of meer RAM vragen. Het besturingssysteem wijst die pagina’s vervolgens toe aan het proces. Dit is echter geen geheugen dat aan uw toepassing is toegewezen. De CRT-geheugentoewijzer zal het geheugen markeren als een aaneengesloten “beschikbaar” blok. De CRT-geheugentoewijzer zal dan door de lijst met vrije blokken lopen en het kleinst mogelijke blok vinden dat het kan gebruiken. Het zal dan zoveel van dat blok nemen als nodig is en het toevoegen aan een “toegewezen” lijst. Aan de kop van de daadwerkelijke geheugentoewijzing wordt een koptekst toegevoegd. Deze header zal verschillende stukjes informatie bevatten (het kan bijvoorbeeld de volgende en vorige toegewezen blokken bevatten om een gekoppelde lijst te vormen. Het zal hoogstwaarschijnlijk de grootte van de toewijzing bevatten).

Free verwijdert dan de header en voegt deze weer toe aan de lijst met vrij geheugen. Als het een groter blok vormt met de omringende vrije blokken, worden deze bij elkaar opgeteld om een groter blok te geven. Als een hele pagina nu vrij is, zal de allocator de pagina hoogstwaarschijnlijk teruggeven aan het besturingssysteem.

Het is geen eenvoudig probleem. Het gedeelte van de OS-toewijzer is volledig buiten uw controle. Ik raad je aan iets als Doug Lea’s Malloc (DLMalloc) door te lezen om te begrijpen hoe een redelijk snelle allocator zal werken.

Bewerken: je crash wordt veroorzaakt doordat je door groter te schrijven dan de toewijzing de volgende geheugenkop hebt overschreven. Op deze manier raakt het bij het vrijmaken erg in de war over wat het precies aan het vrijmaken is en hoe het in het volgende blok moet worden samengevoegd. Dit kan niet altijd direct een crash veroorzaken op de gratis. Het kan later een crash veroorzaken. Vermijd over het algemeen geheugenoverschrijvingen!

Antwoord 11

Je programma loopt vast omdat het geheugen gebruikte dat niet van jou is. Het kan door iemand anders worden gebruikt of niet – als je geluk hebt crash je, anders kan het probleem lange tijd verborgen blijven en later terugkomen en je bijten.

Wat malloc/gratis implementatie betreft – hele boeken zijn gewijd aan het onderwerp. In feite zou de allocator grotere hoeveelheden geheugen van het besturingssysteem krijgen en deze voor u beheren. Enkele van de problemen die een allocator moet aanpakken zijn:

• Hoe nieuw geheugen te krijgen
• Hoe het op te slaan – (lijst of andere structuur, meerdere lijsten voor geheugenblokken van verschillende grootte, enzovoort)
• Wat te doen als de gebruiker om meer geheugen vraagt dan momenteel beschikbaar is (meer geheugen aanvragen bij het besturingssysteem, enkele van de bestaande blokken samenvoegen, hoe ze precies samenvoegen, …)
• Wat te doen als de gebruiker geheugen vrijmaakt
• Debug-toewijzers kunnen je een groter stuk geven dan je hebt aangevraagd en het een bytepatroon vullen, wanneer je het geheugen vrijmaakt, kan de toewijzer controleren of het buiten het blok is geschreven (wat waarschijnlijk in jouw geval gebeurt)
  …

Antwoord 12

Het is moeilijk te zeggen omdat het daadwerkelijke gedrag verschilt tussen verschillende compilers/runtimes. Zelfs debug/release-builds hebben ander gedrag. Debug-builds van VS2005 zullen markeringen tussen toewijzingen invoegen om geheugenbeschadiging te detecteren, dus in plaats van een crash, zal het in free() beweren.

Antwoord 13

Het is ook belangrijk om te beseffen dat het eenvoudigweg verplaatsen van de programmaonderbrekingsaanwijzer met brken sbrkhet geheugen niet daadwerkelijk toewijst, maar stelt gewoon de adresruimte in. Op Linux, bijvoorbeeld, wordt het geheugen “ondersteund” door daadwerkelijke fysieke pagina’s wanneer dat adresbereik wordt geopend, wat zal resulteren in een paginafout en er uiteindelijk toe zal leiden dat de kernel de pageallocator aanroept om een backing-pagina te krijgen.