C dynamisk hukommelsestildeling - C dynamic memory allocation

C standardbibliotek
Generelle emner
Diverse overskrifter

C dynamisk hukommelsestildeling refererer til udførelse af manuel hukommelsesstyring til dynamisk hukommelsestildeling i C -programmeringssproget via en gruppe funktioner i C -standardbiblioteket , nemlig malloc , realloc , calloc og gratis .

Den C ++ programmeringssprog omfatter disse funktioner; de nye og slettede operatører giver dog lignende funktionalitet og anbefales af dette sprogs forfattere. Alligevel er der flere situationer, hvor brug new/deleteikke er relevant, f.eks. Affaldsindsamlingskode eller præstationsfølsom kode, og en kombination af mallocog placement newkan være påkrævet i stedet for newoperatøren på højere niveau .

Mange forskellige implementeringer af den faktiske hukommelsesallokeringsmekanisme, der bruges af malloc , er tilgængelige. Deres ydeevne varierer i både udførelsestid og påkrævet hukommelse.

Begrundelse

Det sprog C programmering styrer hukommelsen statisk , automatisk eller dynamisk . Variabler med statisk varighed tildeles i hovedhukommelsen, normalt sammen med programmets eksekverbare kode, og forbliver i programmets levetid; Variabler med automatisk varighed tildeles på stakken og kommer og går, når funktioner kaldes og returneres. For variabler med statisk varighed og automatisk varighed skal tildelingens størrelse være kompileringstidskonstant (bortset fra automatiske arrays med variabel længde). Hvis den krævede størrelse ikke er kendt før driftstid (f.eks. Hvis data af vilkårlig størrelse læses fra brugeren eller fra en diskfil), er brug af faste objekter i fast størrelse utilstrækkelig.

Den tildelte hukommelses levetid kan også give anledning til bekymring. Hverken statisk eller automatisk varighed er tilstrækkelig til alle situationer. Automatisk tildelte data kan ikke fortsætte på tværs af flere funktionsopkald, mens statiske data vedvarer i programmets levetid, uanset om det er nødvendigt eller ej. I mange situationer kræver programmereren større fleksibilitet i styringen af ​​den tildelte hukommelses levetid.

Disse begrænsninger undgås ved at bruge dynamisk hukommelsestildeling , hvor hukommelse mere eksplicit (men mere fleksibelt) styres, typisk ved at allokere den fra gratis -butikken (uformelt kaldet "bunken"), et hukommelsesområde, der er struktureret til dette formål. I C mallocbruges biblioteksfunktionen til at allokere en hukommelsesblok på bunken. Programmet får adgang til denne hukommelsesblok via en markør, der mallocvender tilbage. Når hukommelsen ikke længere er nødvendig, sendes markøren videre, freesom henviser hukommelsen, så den kan bruges til andre formål.

Den originale beskrivelse af C indikerede det callocog cfreevar i standardbiblioteket, men ikke malloc. Kode til en simpel modelimplementering af en lagerstyring til Unix blev givet med allocog freesom brugergrænsefladefunktioner og ved hjælp af sbrksystemopkaldet til at anmode om hukommelse fra operativsystemet. Den 6. udgave Unix-dokumentation giver allocog freesom funktioner til lavt hukommelsestildeling. Den mallocog freerutiner i deres moderne form er fuldstændig beskrevet i 7. udgave Unix manual.

Nogle platforme leverer biblioteks- eller iboende funktionsopkald , som muliggør dynamisk fordeling i løbetid fra C-stakken frem for bunken (f.eks. alloca()). Denne hukommelse frigøres automatisk, når opkaldsfunktionen slutter.

Oversigt over funktioner

Funktionerne til dynamisk tildeling af C -hukommelse er defineret i stdlib.hheader ( cstdlibheader i C ++).

Fungere Beskrivelse
malloc tildeler det angivne antal bytes
realloc øger eller formindsker størrelsen på den angivne hukommelsesblok og flytter den om nødvendigt
calloc tildeler det angivne antal bytes og initialiserer dem til nul
free frigiver den angivne hukommelsesblok tilbage til systemet

Forskelle mellem malloc()ogcalloc()

  • malloc()tager et enkelt argument (mængden af ​​hukommelse, der skal tildeles i bytes), mens det har calloc()brug for to argumenter (antallet af variabler, der skal tildeles i hukommelsen, og størrelsen i bytes for en enkelt variabel).
  • malloc()initialiserer ikke den allokerede hukommelse, mens den calloc()garanterer, at alle bytes i den tildelte hukommelsesblok er blevet initialiseret til 0.
  • På nogle operativsystemer calloc()kan den implementeres ved i første omgang at pege alle sider i den tildelte hukommelses virtuelle adresser til en skrivebeskyttet side med alle 0'erne og kun tildele læse-skrive fysiske sider, når de virtuelle adresser skrives til, en metode kaldet kopi- på-skrive .

Eksempel på brug

Oprettelse af en matrix med ti heltal med automatisk omfang er ligetil i C: 

int array[10];

Størrelsen af ​​arrayet er dog fastlagt på kompileringstidspunktet. Hvis man ønsker at allokere et lignende array dynamisk, kan følgende kode bruges: 

int *array = (int*)malloc(10 * sizeof(int));

Dette beregner antallet af bytes, som ti heltal optager i hukommelsen, og anmoder derefter om, at mange bytes fra mallocog tildeler resultatet til en markør, der hedder array(på grund af C -syntaks, kan pointer og arrays bruges i flæng i nogle situationer).

Fordi den mallocmuligvis ikke kan betjene anmodningen, returnerer den muligvis en nullmarkør, og det er god programmeringsskik at kontrollere dette: 

int *array = malloc(10 * sizeof(int));
if (array == NULL) {
  fprintf(stderr, "malloc failed\n");
  return -1;
}

Når programmet ikke længere har brug for det dynamiske array , skal det i sidste ende kalde for freeat returnere den hukommelse, det optager til den gratis butik: 

free(array);

Hukommelsen, der er afsat af, initialiseresmalloc ikke og kan indeholde cruft : resterne af tidligere brugte og kasserede data. Efter allokering med er elementer i arrayet uinitialiserede variabler . Kommandoen returnerer en tildeling, der allerede er blevet ryddet: malloccalloc

int *array = calloc(10, sizeof(int));

Med realloc kan vi ændre størrelsen på den hukommelse, en markør peger på. For eksempel, hvis vi har en markør, der fungerer som en matrix af størrelse, og vi vil ændre den til en matrix af størrelse , kan vi bruge realloc. 

int *arr = malloc(2 * sizeof(int));
arr[0] = 1;
arr[1] = 2;
arr = realloc(arr, 3 * sizeof(int));
arr[2] = 3;

Bemærk, at realloc må antages at have ændret basisadressen for blokken (dvs. hvis den ikke har udvidet størrelsen på den originale blok, og derfor har tildelt en ny større blok andre steder og kopieret det gamle indhold til den). Derfor er alle henvisninger til adresser i den originale blok heller ikke længere gyldige.

Type sikkerhed

mallocreturnerer en ugyldig markør ( void *), hvilket angiver, at det er en markør til et område med ukendt datatype. Brug af støbning er påkrævet i C ++ på grund af det stærke typesystem, hvorimod dette ikke er tilfældet i C. Man kan "støbe" (se typekonvertering ) denne markør til en bestemt type: 

int *ptr, *ptr2;
ptr = malloc(10 * sizeof(*ptr)); /* without a cast */
ptr2 = (int *)malloc(10 * sizeof(*ptr)); /* with a cast */

Der er fordele og ulemper ved at udføre et sådant cast.

Fordele ved støbning

  • Inklusiv cast kan muligvis kompilere et C -program eller en funktion som C ++.
  • Den støbte giver mulighed for pre-1989-versioner af mallocdet oprindeligt returnerede en char *.
  • Casting kan hjælpe udvikleren med at identificere inkonsekvenser i typestørrelsen, hvis destinationsmarkørtypen ændres, især hvis markøren erklæres langt fra malloc()opkaldet (selvom moderne kompilatorer og statiske analysatorer kan advare om sådan adfærd uden at kræve cast).

Ulemper ved støbning

  • Under C -standarden er støbningen overflødig.
  • Tilføjelse afstøbningen kan maskere manglende inkludere headeren stdlib.h, hvor funktionsprototypen for mallocer fundet. I mangel af en prototype for mallockræver C90 -standarden, at C -kompilatoren antager, at mallocreturnerer en int. Hvis der ikke er nogen cast, kræver C90 en diagnostik, når dette heltal er tildelt markøren; men med rollelisten ville denne diagnostik ikke blive produceret, hvilket skjulte en fejl. På visse arkitekturer og datamodeller (f.eks. LP64 på 64-bit systemer, hvor longog pointer er 64-bit og inter 32-bit), kan denne fejl faktisk resultere i en udefineret adfærd, da den implicit erklærede mallocreturnerer en 32-bit værdi, hvorimod den faktisk definerede funktion returnerer en 64-bit værdi. Afhængigt af opkaldskonventioner og hukommelseslayout kan dette resultere i stakudbrud . Dette problem er mindre tilbøjeligt til at gå ubemærket hen i moderne kompilatorer, da C99 ikke tillader implicitte erklæringer, så kompilatoren skal fremlægge en diagnostik, selvom den antager intreturnering.
  • Hvis markørens type ændres ved dens erklæring, kan det også være nødvendigt at ændre alle linjer, hvor mallocder kaldes og castes.

Almindelige fejl

Ukorrekt brug af dynamisk hukommelsestildeling kan ofte være en kilde til fejl. Disse kan omfatte sikkerhedsfejl eller programnedbrud, oftest på grund af segmenteringsfejl .

De mest almindelige fejl er som følger:

Kontrollerer ikke for tildelingsfejl
Hukommelsesallokering kan ikke garanteres, og kan i stedet returnere en nullmarkør. Brug af den returnerede værdi uden at kontrollere, om tildelingen er vellykket, påkalder en udefineret adfærd . Dette fører normalt til nedbrud (på grund af den resulterende segmenteringsfejl på nulmarkøren dereference), men der er ingen garanti for, at et nedbrud vil ske, så afhængig af det kan også føre til problemer.
Hukommelse lækker
Manglende tildeling af hukommelse ved hjælp af freefører til opbygning af ikke-genanvendelig hukommelse, som ikke længere bruges af programmet. Dette spilder hukommelsesressourcer og kan føre til tildelingsfejl, når disse ressourcer er opbrugte.
Logiske fejl
Alle tildelinger skal følge det samme mønster: allokering ved hjælp malloc, brug til lagring af data, deallocation ved hjælp af free. Manglende overholdelse af dette mønster, såsom brug af hukommelse efter et opkald til free( dinglende markør ) eller før et opkald til malloc( vild markør ), opkald freeto gange ("dobbelt gratis") osv., Forårsager normalt en segmenteringsfejl og resulterer i en nedbrud af programmet. Disse fejl kan være forbigående og svære at fejlsøge - for eksempel genvinder frigivet hukommelse normalt ikke umiddelbart med det samme af operativsystemet, og dermed hængende pegepinde kan fortsætte et stykke tid og synes at virke.

Derudover har en grænseflade, der går forud for ANSI C -standardisering, mallocog dens tilhørende funktioner adfærd, der med vilje blev overladt til implementeringen at definere for sig selv. En af dem er nullængdetildelingen, hvilket mere er et problem med, reallocda det er mere almindeligt at ændre størrelsen til nul. Selvom både POSIX og Single Unix Specification kræver korrekt håndtering af 0-størrelsesallokeringer ved enten at returnere NULLeller noget andet, der sikkert kan frigøres, er det ikke alle platforme, der skal overholde disse regler. Blandt de mange dobbeltfrie fejl, det har ført til, var WhatsApp RCE 2019 særligt fremtrædende. En måde at pakke disse funktioner på for at gøre dem sikrere er ved blot at tjekke for 0-størrelsesallokeringer og omdanne dem til størrelse 1. (Tilbagevenden NULLhar sine egne problemer: det indikerer ellers en fejl i hukommelsen. I tilfælde af reallocdet ville have signaleret, at den originale hukommelse ikke blev flyttet og frigjort, hvilket igen ikke er tilfældet for størrelse 0, hvilket førte til det dobbelte.)

Implementeringer

Implementeringen af ​​hukommelsesstyring afhænger meget af operativsystem og arkitektur. Nogle operativsystemer leverer en allocator til malloc, mens andre leverer funktioner til at styre bestemte områder af data. Den samme dynamiske hukommelsestildeling bruges ofte til at implementere både mallocog operatøren newi C ++ .

Bunkebaseret

Se også: sbrk

Implementering af allokatoren sker almindeligvis ved hjælp af bunke- eller datasegmentet . Tildelingen vil normalt udvide og kontraktere bunken for at opfylde tildelingsanmodninger.

Bunke -metoden lider af nogle få iboende fejl, der udelukkende stammer fra fragmentering . Ligesom enhver metode til hukommelsestildeling vil bunken blive fragmenteret; det vil sige, at der vil være sektioner af brugt og ubrugt hukommelse i den tildelte plads på bunken. En god tildeler vil forsøge at finde et ubrugt område med allerede tildelt hukommelse, der skal bruges, før han tyer til at udvide bunken. Det største problem med denne metode er, at bunken kun har to væsentlige attributter: base eller begyndelsen af ​​bunken i virtuel hukommelsesplads; og længde eller dens størrelse. Bunken kræver nok systemhukommelse til at fylde hele dens længde, og dens base kan aldrig ændres. Således er alle store områder med ubrugt hukommelse spildt. Bunken kan blive "fast" i denne position, hvis der findes et lille brugt segment for enden af ​​bunken, som kan spilde enhver mængde adresserum. På dovne hukommelsesallokeringsordninger, som dem der ofte findes i Linux -operativsystemet, forbeholder en stor bunke sig ikke nødvendigvis den tilsvarende systemhukommelse; det vil kun gøre det ved det første skrivetidspunkt (læsninger af ikke-kortlagte hukommelsessider returnerer nul). Omfanget af dette afhænger af sidestørrelse.

dlmalloc og ptmalloc

Doug Lea har udviklet det offentlige domæne dlmalloc ("Doug Lea's Malloc") som en allokeret tildeler fra 1987. GNU C-biblioteket (glibc) er afledt af Wolfram Glogers ptmalloc ("pthreads malloc"), en gaffel af dlmalloc med gevindrelaterede forbedringer. Fra november 2019 er den seneste version af dlmalloc version 2.8.6 fra august 2012.

dlmalloc er en grænse tag -allokering. Hukommelse på bunken tildeles som "bidder", en 8-byte justeret datastruktur, der indeholder et overskrift og brugbar hukommelse. Allokeret hukommelse indeholder en 8- eller 16-byte overhead for størrelsen af ​​chunk og brugsflag (ligner en dope-vektor ). Ikke-allokerede bidder gemmer også pointer til andre gratis bidder i det anvendelige rumområde, hvilket gør den mindste delstørrelse 16 bytes på 32-bit systemer og 24/32 (afhænger af justering) bytes på 64-bit systemer.

Ikke-allokeret hukommelse grupperes i " skraldespande " af lignende størrelser, implementeret ved hjælp af en dobbeltkædet liste over bidder (med pointer gemt i det ikke-allokerede rum inde i klumpen). Skriver sorteres efter størrelse i tre klasser:

  • Ved anmodninger under 256 bytes (en "smallbin" -forespørgsel) bruges en simpel allokeringsværktøj med to bedst mulige pasninger. Hvis der ikke er nogen gratis blokke i den bin, deles en blok fra den næsthøjeste bin i to.
  • For anmodninger på 256 bytes eller derover, men under mmap- tærsklen, bruger dlmalloc siden v2.8.0 en bitvis trie- algoritme på stedet ("træbinde"). Hvis der ikke er ledig plads tilbage til at imødekomme anmodningen, at dlmalloc forsøger øge størrelsen af den bunke, som regel via brk systemet opkald. Denne funktion blev introduceret måde efter ptmalloc blev oprettet (fra v2.7.x), og som et resultat er den ikke en del af glibc, som arver den gamle bedst egnede allokeringsenhed.
  • For anmodninger over mmap -tærsklen (en "largebin" -anmodning) tildeles hukommelsen altid ved hjælp af mmap -systemopkaldet . Tærsklen er normalt 256 KB. Den mmap metode averts problemer med enorme buffere fældefangst en lille fordeling i slutningen efter deres udløb, men altid allokerer en hel side af hukommelse, som på mange arkitekturer er 4096 bytes i størrelse.

Spiludvikleren Adrian Stone hævder, at dlmallocsom en grænse-tag-allokering er uvenlig for konsolsystemer, der har virtuel hukommelse, men ikke har efterspørgselssøgning . Dette skyldes, at dets pool-krympende og voksende tilbagekald (sysmalloc/systrim) ikke kan bruges til at allokere og begå individuelle sider i virtuel hukommelse. I mangel af efterspørgsel efterspørgsel bliver fragmentering en større bekymring.

FreeBSD's og NetBSD's jemalloc

Siden FreeBSD 7.0 og NetBSD 5.0 blev den gamle mallocimplementering (phkmalloc) erstattet af jemalloc , skrevet af Jason Evans. Hovedårsagen til dette var mangel på skalerbarhed af phkmalloc med hensyn til multitrådning. For at undgå låsekonflikt bruger jemalloc separate "arenaer" til hver CPU . Eksperimenter, der måler antallet af tildelinger pr. Sekund i multithreading -applikationer, har vist, at dette får det til at skalere lineært med antallet af tråde, mens både ydeevne for phkmalloc og dlmalloc var omvendt proportional med antallet af tråde.

OpenBSD's malloc

OpenBSD 's implementering af mallocfunktionen gør brug af mmap . For anmodninger, der er større end én side, hentes hele allokeringen ved hjælp af mmap; mindre størrelser tildeles fra hukommelsespuljer, der vedligeholdes af mallocinden for et antal "bucket -sider", også tildelt med mmap. På en opfordring til free, er hukommelse frigivet og unmapped fra processen adresseområde hjælp munmap. Dette system er designet til at forbedre sikkerheden ved at udnytte randomiseringen af adresserumslayoutet og gap-sidefunktioner implementeret som en del af OpenBSDs mmap systemopkald og til at opdage brug efter-fri fejl-da en stor hukommelsestildeling er fuldstændig umappet, efter at den er frigivet , yderligere brug forårsager en segmenteringsfejl og afslutning af programmet.

Hoard malloc

Hovedartikel: Hoard memory allocator

Hoard er en tildeler, hvis mål er skalerbar hukommelsesallokeringsevne. Ligesom OpenBSDs allokator bruger Hoard mmapudelukkende, men styrer hukommelse i bidder på 64 kilobytes kaldet superblokke. Hoards bunke er logisk opdelt i en enkelt global bunke og et antal bunker pr. Processor. Derudover er der en tråd-lokal cache, der kan indeholde et begrænset antal superblokke. Ved kun at allokere fra superblokke på den lokale per-thread eller per-processorbunke og flytte for det meste tomme superblocks til den globale bunke, så de kan genbruges af andre processorer, holder Hoard fragmenteringen lav, mens den opnår nær lineær skalerbarhed med antallet af tråde .

mimalloc

Hovedartikel: mimalloc

En open-source kompakt generel hukommelsestildeling fra Microsoft Research med fokus på ydeevne. Biblioteket har omkring 11.000 linjer kode .

Tråd-caching malloc (tcmalloc)

Hver tråd har et tråd-lokalt lager til små tildelinger. Ved store tildelinger kan mmap eller sbrk bruges. TCMalloc , en malloc udviklet af Google, har skraldesamling til lokal opbevaring af døde tråde. TCMalloc anses for at være mere end dobbelt så hurtig som glibc's ptmalloc til multithreaded -programmer.

In-kerne

Operativsystem kerner har brug for at allokere hukommelse, ligesom programmer gør. Implementeringen af mallocinden for en kerne adskiller sig imidlertid ofte væsentligt fra de implementeringer, der bruges af C -biblioteker. For eksempel kan hukommelsesbuffere muligvis være i overensstemmelse med særlige begrænsninger pålagt af DMA , eller hukommelsesallokeringsfunktionen kan blive kaldt fra afbrydelseskontekst. Dette kræver en mallocimplementering, der er tæt integreret med det virtuelle hukommelsessystem i operativsystemkernen.

Overordnet malloc

Fordi mallocog dets pårørende kan have en stærk indflydelse på udførelsen af ​​et program, er det ikke ualmindeligt at tilsidesætte funktionerne for en bestemt applikation ved hjælp af brugerdefinerede implementeringer, der er optimeret til applikations tildelingsmønstre. C -standarden giver ingen måde at gøre dette på, men operativsystemer har fundet forskellige måder at gøre dette på ved at udnytte dynamisk forbindelse. En måde er blot at linke til et andet bibliotek for at tilsidesætte symbolerne. En anden, der anvendes af Unix System V.3 , er at lave mallocog freefungere pointer, som et program kan nulstille til brugerdefinerede funktioner.

Tildeling størrelse grænser

Den størst mulige hukommelsesblok mallockan allokere afhænger af værtsystemet, især størrelsen på den fysiske hukommelse og implementeringen af ​​operativsystemet.

Teoretisk set bør det største antal være den maksimale værdi, der kan holdes i en size_ttype, som er et implementeringsafhængigt usigneret heltal, der repræsenterer størrelsen på et hukommelsesområde. I C99 -standarden og senere er den tilgængelig som SIZE_MAXkonstanten fra <stdint.h>. Selvom det ikke er garanteret af ISO C , er det normalt . 2^(CHAR_BIT * sizeof(size_t)) - 1

På glibc -systemer er den største mulige hukommelsesblok mallockun tildelt halvdelen af ​​denne størrelse, nemlig . 2^(CHAR_BIT * sizeof(ptrdiff_t) - 1) - 1

Udvidelser og alternativer

C -bibliotekets implementeringer, der leveres med forskellige operativsystemer og kompilatorer, kan komme med alternativer og udvidelser til standardgrænsefladen malloc. Bemærkelsesværdig blandt disse er:

  • alloca, som tildeler et efterspurgt antal bytes på opkaldsstakken . Der findes ingen tilsvarende deallocation -funktion, da hukommelsen typisk er dealloceret, så snart den kaldende funktion vender tilbage. allocavar til stede på Unix -systemer allerede i 32/V (1978), men brugen af ​​det kan være problematisk i nogle (f.eks. integrerede) sammenhænge. Selvom den understøttes af mange kompilatorer, er den ikke en del af ANSI-C- standarden og kan derfor ikke altid være bærbar. Det kan også forårsage mindre ydelsesproblemer: det fører til stabelrammer i variabel størrelse, så både stak- og rammepegere skal administreres (med stakrammer i fast størrelse er en af ​​disse redundante). Større tildelinger kan også øge risikoen for udefineret adfærd på grund af et stakoverløb . C99 tilbød arrays med variabel længde som en alternativ stakallokeringsmekanisme-denne funktion blev dog henvist til valgfri i den senere C11- standard.
  • POSIX definerer en funktion, posix_memalignder allokerer hukommelse med opkaldsspecificeret justering. Dens tildelinger er tildelt free, så implementeringen skal normalt være en del af malloc -biblioteket.

Se også

Referencer

eksterne links