För att förstå hur dynamisk minnesallokering (malloc, gratis, calloc, realloc-biblioteksfunktioner) verkligen fungerar finns det inget substitut för att läsa källkoden för malloc () . Det är väl kommenterat:
kommentarer om bitar:
/ * 1056 malloc_chunk detaljer: 1057 1058 (Följande innehåller lätt redigerade förklaringar av Colin Plumb.) 1059 1060 bitar av minne upprätthålls med hjälp av en "gränsmärke" -metod enligt 1061 beskriven i t.ex. Knuth eller Standish. (Se tidningen av Paul1062 Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps för a1063 kartläggning av sådana tekniker.) Storlekar på fria bitar lagras båda 1064 framför varje bit och vid slutet. Detta gör att 1065 konsoliderar fragmenterade bitar till större bitar mycket snabbt. Fälten i storleken 1066 innehåller också bitar som representerar om bitar är fria eller1067 i bruk.1068 1069 En tilldelad bit ser ut så här: 1070 1071 1072 bit-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1073 | Storlek på föregående bit, om det inte är allokerat (P klart) | 1074 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1075 | Storlek på bitar, i byte | A | M | P | 1076 mem-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1077 | Användardata börjar här ... .1078. .1079. (malloc_usable_size () bytes) .1080. | 1081 nextchunk-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1082 | (storleksstorlek, men används för applikationsdata) | 1083 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - +
1084 | Nästa bit, i byte | A | 0 | 1 | 1085 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1086 1087 Där "bit" är den främre delen av delen för det mesta av1088 malloc kod, men "mem" är pekaren som returneras till 1089-användaren. "Nextchunk" är början på nästa angränsande bit.1090 1091 Chunks börjar alltid på jämna ordgränser, så mem-delen1092 (som returneras till användaren) är också på en jämn ordgräns, och1093 därmed åtminstone dubbel-ordad .1094 1095 Gratis bitar lagras i cirkulära dubbelt länkade listor och ser ut så här: 1096 1097 bit-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1098 | Storleken på föregående bit, om den inte är allokerad (P klar) | 1099 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1100 `huvud: '| Storlek på bitar, i byte | A | 0 | P | 1101 mem-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1102 | Vidarebefordra pekaren till nästa bit i listan | 1103 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1104 | Tillbaka pekaren till föregående bit i listan | 1105 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1106 | Oanvändt utrymme (kan vara 0 byte långt) .1107. .1108. | 1109 nextchunk-> + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1110 `fot: '| Storlek på bitar, i byte | 1111 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - +
1112 | Nästa bit, i byte | A | 0 | 0 | 1113 + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + 1114 1115 P (PREV_INUSE) -bit, lagrad i den oanvända lågordningsbiten i 1116-biten storlek (som alltid är en multipel av två ord), är en i1111-bit för * föregående * bit. Om den biten är * klar *, så innehåller1118-ordet före den aktuella klumpstorleken den tidigare klump1119-storleken och kan användas för att hitta framsidan av föregående klump.1120 Den allra första klump som tilldelats har alltid denna bituppsättning, 1121 förhindrar åtkomst till obefintligt (eller icke-ägt) minne. Om1122 prev_inuse är inställd för en viss bit, kan du INTE bestämma1123 storleken på föregående bit och kan till och med få ett minnes1124-adresseringsfel när du försöker göra det.1125 1126 A (NON_MAIN_ARENA) biten rensas för bitar i början 1127 huvudarena, beskriven av variabeln main_arena. När ytterligare1128-trådar skapas får varje tråd sin egen arena (upp till a1129-konfigurerbar gräns, varefter arenor återanvänds för multiple1130-trådar), och bitarna i dessa arenor har A-bituppsättningen. To1131 hitta arenan för en bit på en sådan icke-huvudarena, heap_for_ptr1132 utför en bitmaskering och indirektion genom ar_ptr1133-medlemmen i rubriken per heap heap_info (se arena.c) .1134 1135 Observera att `` foten '' av den aktuella biten representeras faktiskt1136 som föregående storlek på NÄSTA biten. Detta gör det lättare att1137 hantera inriktningar etc men kan vara mycket förvirrande när man försöker1138 att utvidga eller anpassa den här koden.1139 1140 De tre undantagen från allt detta är: 1141 1142 1. Den speciella biten "topp" bryr sig inte om att använda den 1143 bakre storlek fält eftersom det inte finns någon nästa angränsande bit 1144 som skulle behöva indexera det. Efter initialisering, 'top'
1145 tvingas alltid att existera. Om det skulle bli mindre än 1146 MINSIZE byte långt, fylls det på.1147 1148 2. Bitar tilldelade via mmap, som har den näst lägsta ordningen1149 bit M (IS_MMAPPED) inställd i sina storlek fält. Eftersom de tilldelas 1150 en efter en, måste var och en innehålla sitt eget efterföljande storlek1151-fält. Om M-biten är inställd ignoreras de andra bitarna1152 (eftersom mappade bitar varken finns i en arena eller intilliggande1153 till en frigjord bit). M-biten används också för bitar som1154 ursprungligen kom från en dumpad hög via malloc_set_state in1155 krokar .c.1156 1157 3. Bitar i fastboxar behandlas som tilldelade bitar från 1158 synvinkel för bitallokeraren. De konsolideras1159 med sina grannar endast i bulk, i malloc_consolidate.1160 * /
kommentarer om interna datastrukturer:
/ * 1313 ---- ---------------- Interna datastrukturer -------------------- 1314 1315 Allt internt tillstånd hålls i en instans av malloc_state definierad1316 nedan. Det finns inga andra statiska variabler, utom i två valfria1317-fall: 1318 * Om USE_MALLOC_LOCK är definierat, deklareras mALLOC_MUTEx ovan.1319 * Om mmap inte stöder MAP_ANONYMOUS, en dummy-filbeskrivare1320 för mmap.1321 1322 Se upp för många knep som minimera de totala kraven på bokföringsutrymme1323. Resultatet är drygt 1K byte (för 4byte1324-pekare och storlek_t.) 1325 * / 1326 1327 / * 1328 Fack1329 1330 En uppsättning fackhuvuden för gratis bitar. Varje fack är dubbelt 1331 länkat. Facken är ungefär proportionellt (logg) mellanrum. 1332 Det finns många av dessa fack (128). Det här kan se överdrivet ut, men 1333 fungerar mycket bra i praktiken. De flesta lagerplatser innehåller storlekar som är 1334 ovanliga eftersom malloc begär storlek, men är vanligare för fragment1335 och konsoliderade uppsättningar bitar, vilket är vad dessa lagerplatser innehåller, så
1336 kan de hittas snabbt. Alla procedurer bibehåller invarianten1337 att ingen konsoliderad bit fysiskt gränsar till en annan, så varje1338 bit i en lista är känd som föregången och följs av antingen1339 inuse-bitar eller ändarna av minnet.1340 1341 Bitar i soptunnor hålls i storleksordning, med band går till the1342 ungefär minst använda bit. Beställning behövs inte1343 för de små soptunnorna, som alla innehåller bitar av samma storlek, men 1344 underlättar fördelningen av bäst lämpning för större bitar. Dessa lists1345 är bara sekventiella. Att hålla dem i ordning kräver nästan aldrig 1346 tillräcklig genomgång för att garantera att man använder mer avancerade data1347-strukturer. 1348 1349 Bitar av samma storlek är kopplade till de mest1350 som nyligen frigjordes på framsidan, och allokeringar tas från baksidan av 1351. Detta resulterar i LRU (FIFO) -allokeringsordning, som tenderar1352 att ge varje bit lika möjlighet att konsolideras med1353 intilliggande frigjorda bitar, vilket resulterar i större fria bitar och mindre1354-fragmentering.1355 1356 För att förenkla användningen i dubbellänkade listor, varje binhuvud agerar1357 som en malloc_chunk. Detta undviker specialhölje för rubriker.1358 Men för att spara utrymme och förbättra lokalitet, tilldelar vi 1359 endast fd / bk-pekare av lagerplatser och använder sedan ompositioneringstrick1360 för att behandla dessa som fälten i en malloc_chunk * .1361 * / kod >
En av författarna till malloc () , Doug Lea, har skrivit en artikel som heter " A Memory Allocator" som beskriver hur malloc fungerar ( Observera att artikeln är från 2000, så det kommer att finnas lite föråldrad info).
Från artikeln:
Chunks:
Bins :
En ytterligare resurs är kapitel 7: "Memory Allocation" av "Linux Programming Interface" av Michael Kerrisk. TLPI är den bästa referensen av någon typ jag någonsin har stött på och kan inte rekommendera den starkt nog.
Här är ett diagram över implementeringen av malloc () och free () från TLPI:
På en sista anteckning är malloc () ett omslag runt brk () och sbrk () systemanrop, som ändrar storleken på högen genom att ändra platsen för programavbrott.
Från kommentarer i källan:
901 I den nya situationen delas brk () och mmap-utrymme och det finns inga 902 konstgjorda gränser för brk-storlek som införs av kärnan. Dessutom har 903 applikationer börjat använda övergående tilldelningar som är större än 904 128Kb som man föreställde sig 2001. 905 906 Priset för mmap är också högt nu; varje gång glibc mmaps från 907-kärnan tvingas kärnan att nollställa minnet som den ger till 908-applikationen. Nollställning av minne är dyrt och äter mycket cache och 909 minnesbandbredd. Detta har ingenting att göra med effektiviteten hos det virtuella 910-minnessystemet, genom att göra mmap har kärnan inget annat val än 911 till noll. 912 913 2001 hade kärnan en maximal storlek för brk () som var cirka 800 914 megabyte på 32 bitars x86, då skulle brk () träffa de första 915 mmformade delade biblioteken och kunde inte expandera längre. Med nuvarande 2,6 916 kärnor är VA-rymdlayouten annorlunda och brk () och mmap 917 kan båda spänna över hela högen efter behag. 918 919 I stället för att använda en statisk tröskel för brk / mmap-avvägningen använder vi 920 nu en enkel dynamisk. Målet är fortfarande att undvika 921-fragmentering. De gamla målen vi höll är 922 1) försök att få de långlivade stora tilldelningarna för att använda mmap () 923 2) riktigt stora tilldelningar bör alltid använda mmap () 924 och vi lägger till nu: 925 3) övergående tilldelningar ska använda brk () för att undvika att tvinga kärnan 926 att behöva nollställa minne om och om igen 927 928 Implementeringen fungerar med en glidtröskel, vilket är som standard
929 begränsad till att gå mellan 128Kb och 32Mb (64Mb för 64 bitmaskiner) och startar 930 ut vid 128Kb enligt 2001 års standard. 931 932 Detta gör det möjligt för oss att uppfylla krav 1) under antagandet att långa 933 levda tilldelningar görs tidigt i processens livslängd, innan det har 934 börjat göra dynamiska tilldelningar av samma storlek (vilket kommer 935 att öka tröskeln). 936 937 Den övre gränsen på tröskeln uppfyller kravet 2) 938 939 Tröskeln ökar i värde när applikationen frigör minne som tilldelades 940 till mmap-allokeraren. Tanken är att när applikationen 941 börjar frigöra minne av en viss storlek är det mycket troligt att detta är 942 en storlek som applikationen använder för övergående tilldelningar. Denna estimator 943 är där för att uppfylla det nya tredje kravet. 944 945 * /