ããå¨å®ç°mallocä¹åï¼å è¦ç¸å¯¹æ£å¼å°å¯¹mallocåä¸ä¸ªå®ä¹ã
ããæ ¹æ®æ åCåºå½æ°çå®ä¹ï¼mallocå ·æå¦ä¸ååï¼
void* malloc(size_t size);
ããè¿ä¸ªå½æ°è¦å®ç°çåè½æ¯å¨ç³»ç»ä¸åé ä¸æ®µè¿ç»çå¯ç¨çå åï¼å ·ä½æå¦ä¸è¦æ±ï¼
mallocåé çå å大å°è³å°ä¸ºsizeåæ°ææå®çåèæ°
mallocçè¿åå¼æ¯ä¸ä¸ªæéï¼æåä¸æ®µå¯ç¨å åçèµ·å§å°å
å¤æ¬¡è°ç¨mallocæåé çå°åä¸è½æéå é¨åï¼é¤éæ次mallocæåé çå°å被éæ¾æ
mallocåºè¯¥å°½å¿«å®æå ååé 并è¿åï¼ä¸è½ä½¿ç¨NP-hardçå ååé ç®æ³ï¼
å®ç°mallocæ¶åºåæ¶å®ç°å å大å°è°æ´åå åéæ¾å½æ°ï¼å³reallocåfreeï¼
ãã对äºmallocæ´å¤ç说æå¯ä»¥å¨å½ä»¤è¡ä¸é®å ¥ä»¥ä¸å½ä»¤æ¥çï¼
man malloc
ããé¦å æ们è¦ç¡®å®æéç¨çæ°æ®ç»æãä¸ä¸ªç®åå¯è¡æ¹æ¡æ¯å°å å å空é´ä»¥åï¼Blockï¼çå½¢å¼ç»ç»èµ·æ¥ï¼æ¯ä¸ªåç±metaåºåæ°æ®åºç»æï¼metaåºè®°å½æ°æ®åçå ä¿¡æ¯ï¼æ°æ®åºå¤§å°ã空é²æ å¿ä½ãæéççï¼ï¼æ°æ®åºæ¯çå®åé çå ååºåï¼å¹¶ä¸æ°æ®åºç第ä¸ä¸ªåèå°åå³ä¸ºmallocè¿åçå°åã
ããå¯ä»¥ç¨å¦ä¸ç»æä½å®ä¹ä¸ä¸ªblockï¼
typedef struct s_block *t_block;
struct s_block {
size_t size; /* æ°æ®åºå¤§å° */
t_block next; /* æåä¸ä¸ªåçæé */
int free; /* æ¯å¦æ¯ç©ºé²å */
int padding; /* å¡«å
4åèï¼ä¿è¯metaåé¿åº¦ä¸º8çåæ° */
char data[1] /* è¿æ¯ä¸ä¸ªèæå段ï¼è¡¨ç¤ºæ°æ®åç第ä¸ä¸ªåèï¼é¿åº¦ä¸åºè®¡å
¥meta */
};
ããç±äºæ们åªèè64ä½æºå¨ï¼ä¸ºäºæ¹ä¾¿ï¼æ们å¨ç»æä½æåå¡«å ä¸ä¸ªintï¼ä½¿å¾ç»æä½æ¬èº«çé¿åº¦ä¸º8çåæ°ï¼ä»¥ä¾¿å å对é½ã示æå¾å¦ä¸ï¼
ããç°å¨èèå¦ä½å¨blocké¾ä¸æ¥æ¾åéçblockãä¸è¬æ¥è¯´æ两ç§æ¥æ¾ç®æ³ï¼
First fitï¼ä»å¤´å¼å§ï¼ä½¿ç¨ç¬¬ä¸ä¸ªæ°æ®åºå¤§å°å¤§äºè¦æ±sizeçåæè°æ¤æ¬¡åé çå
Best fitï¼ä»å¤´å¼å§ï¼éåææåï¼ä½¿ç¨æ°æ®åºå¤§å°å¤§äºsizeä¸å·®å¼æå°çåä½ä¸ºæ¤æ¬¡åé çå
ãã两ç§æ¹æ³åæåç§ï¼best fitå ·æè¾é«çå å使ç¨çï¼payloadè¾é«ï¼ï¼èfirst fitå ·ææ´å¥½çè¿è¡æçãè¿éæ们éç¨first fitç®æ³ã
/* First fit */
t_block find_block(t_block *last, size_t size) {
t_block b = first_block;
while(b && !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return b;
}
ããfind_blockä»frist_blockå¼å§ï¼æ¥æ¾ç¬¬ä¸ä¸ªç¬¦åè¦æ±çblock并è¿åblockèµ·å§å°åï¼å¦ææ¾ä¸å°è¿è¿åNULLãè¿éå¨éåæ¶ä¼æ´æ°ä¸ä¸ªå«lastçæéï¼è¿ä¸ªæéå§ç»æåå½åéåçblockãè¿æ¯ä¸ºäºå¦ææ¾ä¸å°åéçblockèå¼è¾æ°block使ç¨çï¼å ·ä½ä¼å¨æ¥ä¸æ¥çä¸èç¨å°ã
ããå¦æç°æblocké½ä¸è½æ»¡è¶³sizeçè¦æ±ï¼åéè¦å¨é¾è¡¨æåå¼è¾ä¸ä¸ªæ°çblockãè¿éå ³é®æ¯å¦ä½åªä½¿ç¨sbrkå建ä¸ä¸ªstructï¼
#define BLOCK_SIZE 24 /* ç±äºåå¨èæçdataå段ï¼sizeofä¸è½æ£ç¡®è®¡ç®metaé¿åº¦ï¼è¿éæ工设置 */
t_block extend_heap(t_block last, size_t s) {
t_block b;
b = sbrk(0);
if(sbrk(BLOCK_SIZE + s) == (void *)-1)
return NULL;
b->size = s;
b->next = NULL;
if(last)
last->next = b;
b->free = 0;
return b;
}
ããFirst fitæä¸ä¸ªæ¯è¾è´å½ç缺ç¹ï¼å°±æ¯å¯è½ä¼è®©å¾å°çsizeå æ®å¾å¤§çä¸åblockï¼æ¤æ¶ï¼ä¸ºäºæé«payloadï¼åºè¯¥å¨å©ä½æ°æ®åºè¶³å¤å¤§çæ åµä¸ï¼å°å ¶åè£ä¸ºä¸ä¸ªæ°çblockï¼ç¤ºæå¦ä¸ï¼
ããå®ç°ä»£ç ï¼
void split_block(t_block b, size_t s) {
t_block new;
new = b->data + s;
new->size = b->size - s - BLOCK_SIZE ;
new->next = b->next;
new->free = 1;
b->size = s;
b->next = new;
}
ããæäºä¸é¢ç代ç ï¼æ们å¯ä»¥å©ç¨å®ä»¬æ´åæä¸ä¸ªç®åä½åæ¥å¯ç¨çmallocã注æé¦å æ们è¦å®ä¹ä¸ªblocké¾è¡¨ç头first_blockï¼åå§å为NULLï¼å¦å¤ï¼æ们éè¦å©ä½ç©ºé´è³å°æBLOCK_SIZE + 8ææ§è¡åè£æä½ã
ããç±äºæ们å¸æmallocåé çæ°æ®åºæ¯æ8åè对é½ï¼æ以å¨sizeä¸ä¸º8çåæ°æ¶ï¼æ们éè¦å°sizeè°æ´ä¸ºå¤§äºsizeçæå°ç8çåæ°ï¼
size_t align8(size_t s) {
if(s & 0x7 == 0)
return s;
return ((s >> 3) + 1) << 3;
}
#define BLOCK_SIZE 24
void *first_block=NULL;
/* other functions... */
void *malloc(size_t size) {
t_block b, last;
size_t s;
/* 对é½å°å */
s = align8(size);
if(first_block) {
/* æ¥æ¾åéçblock */
last = first_block;
b = find_block(&last, s);
if(b) {
/* å¦æå¯ä»¥ï¼ååè£ */
if ((b->size - s) >= ( BLOCK_SIZE + 8))
split_block(b, s);
b->free = 0;
} else {
/* 没æåéçblockï¼å¼è¾ä¸ä¸ªæ°ç */
b = extend_heap(last, s);
if(!b)
return NULL;
}
} else {
b = extend_heap(NULL, s);
if(!b)
return NULL;
first_block = b;
}
return b->data;
}