鑒於上次領導告訴一個解決方案，讓我把它寫成文檔，結果自己腦子裡知道如何操作和解決，但就是不知道如何用語言文字把它給描述出來。決定以後多寫一些筆記和微博來鍛煉自己的文字功底和培養邏輯思維，不然只會是一個敲代碼的，永遠到不了管理的層面。
把《C程序設計語言》細讀了一遍後，到第8章UNIX系統接口的最後兩節——“目錄列表”和“存儲分配程序”，看了一遍都沒看懂。智商不過高啊。把存儲分配重新看了一遍，才有了眉頭。這兩天還要找時間把目錄列表再看一遍，確保掌握。（前幾章節有些地方看了很多遍也糊裡糊塗，就找谷歌百度幫忙了）
這裡的存儲分配程序，講的就是標准庫中malloc函數的實現原理。首先要了解針對malloc的內存存儲結構。malloc不像全局變量一樣，不是在編譯器編譯的時候就會分配內存空間，而是在調用到malloc函數時才會分配空間。有時還會中途調用free函數釋放空間出來。所以：
1、malloc在第一次被調用時，從系統中獲取最小為一個單元的空閒空間（eg：最小單元為1024個最受限單元塊。當x<=1024，獲取1024個，否則獲取x個），再進行分配；
2、malloc所剩下的空閒空間一般都不是連續的，而是分散的。這樣也提高了空間的利用率。
為了管理malloc的空閒空間，每一個獨立塊的最前面都包含了一個“頭部”信息：一個指向下一個空閒塊的指針、一個本身獨立塊的長度（書上說還有一個指向自身存儲空間的指針，但每個存儲空間都有自身的指針，為什麼還要這個呢。後看英語版原著，這麼寫的：Each block contains a size, a pointer to nextblock, and the space itself.）。下一個空閒塊是按存儲地址升序排列，離本空閒塊最近的一個空閒塊，若本空閒塊在最後，則指向最前的空閒塊。這樣所有屬於malloc的空閒空間都被串在了一起。如下圖所示：
<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+16KjutbQzsSw5rXEtMvNvL3iys23rdLruOO07cHLo6zI58/CzbyjujwvcD4KPHA+PGltZyBzcmM9"/uploadfile/Collfiles/20141113/20141113091213197.jpg" alt="\">
因為後面的free函數已經把相鄰的空閒鏈表給整合成一塊了，所以我的圖沒有出現相鄰的空閒鏈表。
每塊由malloc控制的空間都包含一個“頭部”信息，為了方便管理，每塊的空間大小都是頭部大小的整數倍。而頭部長度=指向下一個空閒塊的指針的長度+自身空間大小的unsigned長度。但為了確保由malloc函數返回的存儲空間滿足將要保存的對象的對齊要求。每個機器都有一個最受限的類型：如果最受限的類型可以存儲在某一個特定的地址中，則其他所有的類型也可以存放在此地址中。有的是double型，有的是long型，甚至還有的是int型。因此，頭部結構將與最受限的類型進行聯合，來確保對齊。
因為有頭部信息，頭部信息裡的本塊空間size也是包括頭部的大小，所以每次申請malloc空閒塊的時候，都要加上一個單元，最後返回給用戶的時候，再去掉頭部。
每次調用malloc申請空間時，malloc有一個專門指向當前空閒塊鏈表的靜態指針freep。從當前開始掃描剩下的空閒塊鏈表，直到掃到一個足夠大的空閒塊。此算法成為“首次適應”（first fit），與之相對的是“最佳適應”（best fit）：它將掃描出滿足條件最小的塊。這裡的代碼是“首次適應”算法。結果將出現三種情況：
1）找到一塊剛好合適的空閒塊，則此塊空間從鏈表中移走並將此塊的地址返回給用戶，並把靜態指針freep指向前一空閒塊地址；
2）找到一塊比需求大的空閒塊，則從此空閒塊中的後部取一塊與需求一樣的空間給用戶，前部改變空閒塊大小便可；
注（直到寫本博文才發現自己錯了）：
①一直都認為返回給用戶地址前一單元的頭部，應該把空間退還給前面的空閒塊，不然就閒著了。其實，裡面記錄了一個重要信息：空間塊大小（包括頭部和返回給用戶的單元大小），在free釋放空間的時候，就必須用到此頭部的信息；
②後面的free程序以為是專供系統申請空間後插入空閒塊鏈表用的，其實它就是我們平常用malloc、realloc、或calloc申請空間後，再釋放的程序。
3）如果掃描了一遍，都沒有找到足夠大的空閒塊，則向系統再申請一塊新的空間。
上面都是在malloc已經有了空閒塊的前提下，但第一次申請的時候，malloc是沒有空閒塊空間的。因此，在預編譯時，就建立了一個單元的空閒塊鏈表base來當做空閒鏈表的入口。當第一次調用malloc時，空閒鏈表的靜態指針freep為NULL，那將它指向base，大小設為0（這樣這塊base空間將一直存在，且不被申請，確保了之後freep一直指向有效的空閒塊鏈表），且指向它自己，同時向系統申請空閒空間（每次向系統申請的空間都是一塊連續的空閒塊）。
typedef long Align; /*按照long類型的邊界對齊，即以long作為最受限類型*/
union header{ /*頭部信息*/
struct {
union header *ptr; /*指向下一個空閒塊*/
unsigned size; /*本空閒塊大小*/
}s;
Align x; /*強制對齊*/
};
typedef union header Header;
static Header base; /*第一次調用malloc的空閒塊鏈表入口，大小為0的空鏈表（按照上面邏輯的來說，這裡的size應該為1）*/
static Header *freep = NULL; /*靜態的空閒塊鏈表指針，初始化為NULL。第一次申請後才會指向base*/
/*malloc函數：通用存儲分配函數*/
void *malloc(unsigned nbytes)
{
Header *p,*prevp; /*定義一個當前空閒塊指針變量，和前一個空閒塊指針變量*/
Header *morecore(unsigned); /*用於向系統申請空閒空間函數*/
unsigned nunits; /*需要申請的實際單元大小，即上面圖中的z*/
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1; /*與上圖對應，把字節大小轉換為單元大小，向上取整，並加上一個單元（頭部）*/
if((prevp = freep) == NULL){ /*沒有空閒鏈表，第一次申請*/
base.s.ptr = prevp = freep = &base; /*freep指向base，base的下一個空閒塊指針指向自己*/
base.s.size =0; /*設置大小為0*/
}
for(p = prevp->s.ptr;;prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){
if(p->s.size == nunits) /*大小剛好合適*/
prevp->s.ptr = p->s.ptr; /*移走此塊空閒區域*/
else{ /*比實際需求大，從空閒塊尾部分配*/
p->s.size -= nunits; /*縮小空閒塊大小*/
p += p->s.size; /*指針指向被申請的空間的頭部*/
p->s.size = nunits; /*設置被申請的空閒塊大小*/
}
freep =prevp; /*當前靜態指針指向前一空閒塊，如果當前塊還有空閒區域，下次將繼續從此處開始掃描，節省時間*/
return (void *)(p+1); /*返回去頭部單元的空閒空間*/
}
if(p == freep) /*閉環的空閒鏈表，第一次調用malloc申請，或掃描一遍，未發現足夠大的空間*/
if((p = morecore(nunits)) == NULL) /*向系統申請空間*/
return NULL; /*未申請成功，*/
}
}
通過下面的morecore()和free()函數的程序分析可知，在向系統成功申請空間後，p將指向有足夠空間的空閒塊。但在此代碼中，進入下一此空閒塊掃描前，p將指向下一塊不足的空閒塊，導致多掃描了一遍。個人覺得，如果空間足夠，可以多申請一個靜態指針beforefreep，指向freep的前一個空閒塊。這樣上面代碼可添加一句，提高效率：
if(p == freep){ /*這樣要添加大括號*/
if((p = morecore(nunits)) == NULL)
return NULL;
p = beforefreep;
}
或
if(p == freep) /*這裡可以不用加大括號，else與最近的if匹配*/
if((p = morecore(nunits)) == NULL)
return NULL;
else
p = beforefreep;
向系統申請空間的時，不是按需分配，而是有一個最小申請單元數。讓您足夠用，這次用不完可以留著下次用，不用每次都向系統申請，又不會系統浪費空間。
真正向系統申請空間，還需調用系統調用sbrk(n)（UNIX下），若申請成功，該指針返回指向n個字節的存儲空間；若申請失敗，返回-1（不是NULL）。返回的指針類型是char *（應該是最小的存儲空間單元）。
#define NALLOC 1024 /*最小申請單元數*/
/*morecore函數：向系統申請更多的存儲空間*/
static Header *morecore(unsigned nu) /*返回的是靜態空閒塊鏈表指針*/
{
char *cp, *sbrk(int);
Header *up;
if(nu < NALLOC)
nu =NALLOC;
cp = sbrk(nu * sizeof(Header)); /*調用系統調用申請系統空間*/
if(cp == (char *) -1)
return NULL; /*申請失敗，沒有空間*/
up = (Header *)cp; /*轉換為Header*指針類型*/
up->s.size = nu; /*設置此空間塊的大小*/
free((void *)(up +1)); /*釋放空間*/
return freep;
}
這裡的返回的freep，在free中更新了，才返回的。當初也想過既然freep都是靜態全局變量了，那這裡為什麼還要返回一個靜態變量呢，直接在函數裡賦值就好了。其實這裡有成功與失敗，所以程序來需要判斷申請結果，而且返回的freep是與申請最相關東西。
free(void *ap)函數就是釋放指針ap所指的空間，具體要釋放的大小在ap前一個指針，即頭部信息裡。釋放主要就是為了把此空間插入到空閒塊鏈表中。所以要找到此空間塊兩邊的空閒塊（也有可能只有一塊空閒塊，即入口base）。然後判斷是否與前一塊相連，與後一塊相連，相連的話，合並成一塊，否則直接在中間插入一個新的空閒塊鏈表。
/*free函數：釋放ap，將ap塊放入空閒鏈表中*/
void free(void *ap)
{
Header *p, *bp;
bp =(Header *)ap -1; /*指向ap塊的頭部*/
for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) /*找到bp所在空閒鏈表中的位置*/
if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)) /*判斷是否在鏈表的開頭或末尾*/
break;
if(bp + bp->s.size == p->s.ptr){ /*先判斷能否與高地址的空閒塊合並，即與後一塊合並*/
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
}
else
bp->s.ptr = p->s.ptr; /*不能合並，bp指向後一塊地址*/
if(p + p->s.size == bp){ /*再判斷能否與地地址的空閒塊合並，即與前一塊合並*/
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
}
else
p->s.ptr =bp; /*不能合並，p指向bp地址*/
freep =p;
}
注：中文版翻譯的又有歧義了，原著分別是“join to upper nbr”和“jointo lower nbr”。
這個free程序，處理的太妙了。一般思維，先與前一塊合並，再與下一塊合並，如下面的程序（顯然比我的好多了）：
if(p + p->s.size == bp){ /*與前一塊相連？*/
if(bp + bp->s.size == p->s.ptr){ /*與後一塊相連？*/
p->s.size += bp->s.size + p->s.ptr->s.size;
p->s.ptr = p->s.ptr->s.ptr;
}else
p->s.size += bp->s.size;
}else{
if(bp + bp->s.size == p->s.ptr){ /*與後一塊相連？*/
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
p->s.ptr = bp;
}else /*不與任何一塊相連*/
bp->s.ptr = p->s.ptr;
p->s.ptr = bp;
}
從這裡可以看出，通過malloc申請後的空間，並沒有初始化，所以在使用前記得初始化，不小心當做右值使用，出錯的概率很大。
《C程序設計語言》（第2版·新版）不愧是經典，值得細讀和鞏固。感謝作者！
寫了很久才寫完，有錯誤或不好的地方，歡迎各位指正和批評！也感謝您花時間閱讀！
