/*如果你使用linux, douglea malloc已經默認作為glibc的malloc,

新的版本可能用的是ptmalloc(dlmalloc的多線程版本)

如果你用的bsd4.2及以前系統libc用的kingsley的malloc;

BSD(包括freebsd,netbsd,openbsd)4.2以后版本libc用的是PHKmalloc;

如果你用的windows系統用的是microsoft的分配器算法;

不過其他各個系統很容易使用doug lea malloc替換現有的malloc*/

//c語言標準庫提供的malloc函數；請注意malloc的幾個return出口;

void* mALLOc(size_t bytes)

{

//0~4bytes->nb=16;>4bytes->nb=bytes+2個4字節頭，然后對其到8bytes

checked_request2size(bytes, nb);

//如果在fastbin中有可用的塊直接從fastbin中分配

if ((unsigned long)(nb) <= (unsigned long)(av->max_fast)) {

fb = &(av->fastbins[(fastbin_index(nb))]);

if ( (victim = *fb) != 0) { //靜態變量成員fastbin初始化為0

*fb = victim->fd;

check_remalloced_chunk(victim, nb);

return chunk2mem(victim);

}

}

//如果是<512bytes的小塊請求,從smallbin中取一塊

if (in_smallbin_range(nb))

{

//根據nb大小定位到smallbin

idx = smallbin_index(nb);

bin = bin_at(av,idx);

//如果該大小的bin列表不為空

if ( (victim = last(bin)) != bin)

{

if (victim == 0) //靜態變量成員smallbin初始化是0

malloc_consolidate(av);//第一次進來這里調用init_state函數進行初始化

else {//有空閑塊

/* victim

|

\/

bin->first_chunk->chunk->chunk->...->last_chunk

| /\

--------------------------------->|

*/

//按上圖將victim從鏈表中刪除,設置victim的下一塊的pbit=inuse

//將victim塊返回給應用

return chunk2mem(victim);

}

}

}

else {//>512bytes,先釋放fastbin中的塊

idx = largebin_index(nb);

if (have_fastchunks(av)) //初始化的時候靜態變量0，這個條件成立，

malloc_consolidate(av); //合并fastbin中的chunk,放入unsorted_bin

}

//這里是唯一將chunks放入bin的地方

//處理最近被釋放或剩余的chunks，如果上次小請求沒有完全匹配

//分割出小chunk就會發生

//最外面的for(;;)需要，因為我們無法知道在malloc結束前有合并操作

//因此需要多嘗試一次，最多多循環一次

for(;;){

/*

unsorted chunks，所有的從一個chunk中分割出來的剩余chunk首先放到

unsorted chunks鏈表中，下次malloc調用中有一次被再次使用的機會。

作為一個隊列維護。

當free或malloc_consolidate函數中 將剩余chunk放入unsorted chunks鏈表，

而在malloc函數中被分配或放入其他 正常bin中。

*/

//循環unsorted中每一塊，與插入順序相反，從后面開始匹配查找

while ( (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {

bck = victim->bk;//victim:unsorted's last chunk;bck:unsorted's last-two chunk

size = chunksize(victim);

if (in_smallbin_range(nb) //<512bytes

&& bck == unsorted_chunks(av) //unsorted隊列中只有一塊

&& victim == av->last_remainder //并且這一塊是上一次分割剩下的

&& (unsigned long)(size) > (unsigned long)(nb + MINSIZE)) //剩余的chunk必須大于MINSIZE

{

//分割nb出去，剩余的繼續放在reminder和unsorted中

return chunk2mem(victim);

}

//unsorted_bin中多于一塊chunk,或者剩余一塊但不是上一次分割剩余的

//或者剩余的一塊大小太小，繼續向下

//把最后一塊從unsorted freelist中刪除

unsorted_chunks(av)->bk = bck;

bck->fd = unsorted_chunks(av);

//如果正好完全匹配，則return

if (size == nb) {

set_inuse_bit_at_offset(victim, size);

check_malloced_chunk(victim, nb);

return chunk2mem(victim);

}

//不是完全匹配就從unsorted_bin移到normal_bin中

if(in_smallbin_range(size)){}

else//注意large-bin中的內存塊是有序的,FIFO

{}

}//end while

//對于<512bytes的請求,使用best-fit策略查找當前bin

//注意當前bin是根據應用請求的size直接index定位到的bin

if (!in_smallbin_range(nb)) {//best-fit

if ((victim = last(bin)) != bin //empty or //first最大，但也不能滿足請求

&&(unsigned long)(first(bin)->size) >= (unsigned long)(nb)) {

//從后往前找，找到第一個滿足請求的

while (((unsigned long)(size = chunksize(victim)) < (unsigned long)(nb)))

victim = victim->bk;

//如果剩余的大小

if (remainder_size < MINSIZE) {

return chunk2mem(victim);

}

else{//分割該塊,返回給應用,剩余的塊 放入unsorted-bin

return chunk2mem(victim);

}

}

}

//如果unsorted-bin,當前bin都沒有滿足的,依次查找下一個更大的bin，直到找到一個滿足的為止

for (;;) {

//這里使用了bitmap技巧快速查找到匹配的large-bin,具體信息可以參考其他文章

//bit > map說明這個32位中bit后面的bin都是空

/*bit==0??啥意思,index%32==0

index->bit

32 ->1 2^0

1 ->2 2^1

2 ->4 2^2

...

31 -> 2^31

*/

if (bit > map || bit == 0) {//bit怎么會是0??? //從下一個32開始

do {

if (++block >= BINMAPSIZE) /* out of bins */

goto use_top; //所有bin都找完了還沒找到,跳到下面use_top

} while ( (map = av->binmap[block]) == 0);

bin = bin_at(av, (block << BINMAPSHIFT));

bit = 1;//從第一位開始

}

//......

//如果找到一塊滿足的，將該塊進行分割

//如果剩余的大小

if (remainder_size < MINSIZE) {

return chunk2mem(victim);

}

else{//分割該塊,返回給應用,剩余的塊 放入unsorted-bin

return chunk2mem(victim);

}

}//end for(;;),遍歷normal-bin

//如果所有bin都沒有可用的塊

use_top:

//如果top足夠大,從top取一塊return給用戶，修改top指針

if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {

return chunk2mem(victim);

}

//上面入口處如果請求>512bytes會觸發合并fastbin

//在這里:如果fastbins無法滿足,smallbins也無法滿足,

//而后合并fastbins放入unsorted_bins,

//對于大塊再到unsorted_bins找,如果沒有精確匹配放入normal_bin

//然后再到normal_bins找best-fit

//如果還沒找到，擴展top

//由此可知，如果請求smallsize，則不會觸發上述合并fastbins，

//然后會觸發到unsorted_bins查找，只有一塊上次剩余的小塊才會

//被分配，或者精確匹配，否則放入normal_bins

//然后不管larger或small都到normal_bins中查找

//所以在這里對fastbins合并再嘗試一次

else if (have_fastchunks(av)) {

assert(in_smallbin_range(nb));

malloc_consolidate(av);

idx = smallbin_index(nb); /* restore original bin index */

}

else //top也沒法滿足，向OS擴展內存

return sYSMALLOc(nb, av);

}

}//最外層的for(;;)

//end

}