[OS64][034] 源碼閱讀：程序9-1 通用內(nèi)存分配函數(shù) kmalloc()

學(xué)習(xí)筆記

使用教材（配書源碼以及使用方法）
《一個(gè)64位操作系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)》
http://www.ituring.com.cn/book/2450
http://www.itdecent.cn/p/28f9713a9171

源碼結(jié)構(gòu)

  • 配書代碼包 ：第9章 \ 程序 \ 程序9-1

為什么要有函數(shù) kmalloc() ？

  • 內(nèi)核想要申請(qǐng)空間，但是不想要一整頁那么多的，只想申請(qǐng)一些少的空間時(shí)用到kmalloc；
  • 這里的"少"是針對(duì)一張物理頁2MB的容量來講的， 比2MB的數(shù)值小在這里就叫做字節(jié)數(shù)少；
  • kmalloc() 就負(fù)責(zé)分配這些一小塊、一小塊的內(nèi)存空間；

一、slab_init()：為Kmalloc_cache_size[] 手動(dòng)創(chuàng)建靜態(tài)存儲(chǔ)空間

slab_init()：為Kmalloc_cache_size[] 手動(dòng)創(chuàng)建靜態(tài)存儲(chǔ)空間.png
  • 內(nèi)存池?cái)?shù)組Kmalloc_cache_size[] 位于內(nèi)核層；
  • 在memory_management_struct.end_of_struct開始，創(chuàng)建與數(shù)組元素一一對(duì)應(yīng)的struct Slab結(jié)構(gòu)體、填充空間及其color_map位圖，一共是16個(gè)；
  • 從物理地址2MB開始，創(chuàng)建與數(shù)組元素一一對(duì)應(yīng)的存儲(chǔ)空間，一張物理頁2MB全部空間都拿來做存儲(chǔ)空間，每個(gè)內(nèi)存對(duì)象的大小（即每次分配的字節(jié)數(shù)）是Kmalloc_cache_size[i].size字節(jié);
unsigned long slab_init()
{
. . .
內(nèi)存池 [i] 已經(jīng)分配了多少個(gè)內(nèi)存對(duì)象，這里初始化置 0
        kmalloc_cache_size[i].cache_pool->using_count = 0;

內(nèi)存池 [i] 還有多個(gè)內(nèi)存對(duì)象可以分配，每分配一次，free_count--
        kmalloc_cache_size[i].cache_pool->free_count  
            = PAGE_2M_SIZE / kmalloc_cache_size[i].size;

color_map 中每一位對(duì)應(yīng)一個(gè)內(nèi)存對(duì)象的分配情況
已分配的內(nèi)存對(duì)象，位圖對(duì)應(yīng)bit 置 1
需要用 “color_length 個(gè) unsigned long 變量” 表示 整張位圖
        kmalloc_cache_size[i].cache_pool->color_length 
                  =((PAGE_2M_SIZE / kmalloc_cache_size[i].size + sizeof(unsigned long) * 8 - 1) >> 6) << 3;

用來記錄最初有多個(gè)空閑對(duì)象（這里設(shè)置初始化之后，不會(huì)再變化）
        kmalloc_cache_size[i].cache_pool->color_count 
          = kmalloc_cache_size[i].cache_pool->free_count;
 
. . .
}

二、kmalloc() 以及 kmalloc_create()

  • kmalloc( ) 會(huì)返回申請(qǐng)到的存儲(chǔ)空間地址(線性地址)

  • kmalloc _create( )會(huì)返回創(chuàng)建的slab 的線性地址，一個(gè)新建的slab 意味著帶來新鮮的許多空閑對(duì)象可分配

  • 存儲(chǔ)空間包括：slab_init() 創(chuàng)建的靜態(tài)空間 + 隨后由kmalloc_create()創(chuàng)建的動(dòng)態(tài)空間；

  • 分支零：于slab_init()時(shí)期，手動(dòng)創(chuàng)建的靜態(tài)存儲(chǔ)空間還夠用，那就直接從這些靜態(tài)存儲(chǔ)空間分配內(nèi)存對(duì)象給申請(qǐng)者；

  • 分支一：存儲(chǔ)空間不夠了，申請(qǐng)者一次需要<=512B 的內(nèi)存；

  • 分支二：存儲(chǔ)空間不夠了，申請(qǐng)者一次需要>512B & <= 1MB的內(nèi)存；

void * kmalloc(unsigned long size,unsigned long gfp_flages)
{

1、遍歷16個(gè)內(nèi)存池，找到容量剛剛好比申請(qǐng)的size大的最小的內(nèi)存池，找到那個(gè)管理存儲(chǔ)空間的那個(gè)slab
    for(i = 0;i < 16;i++)
        if(kmalloc_cache_size[i].size >= size)
            break;
    slab = kmalloc_cache_size[i].cache_pool;

2、是否有空閑？有就進(jìn)入if{ }，沒有就進(jìn)入else{ }
2.1 一進(jìn)入if{ } ，就馬上執(zhí)行do{  } ， 即先看靜態(tài)創(chuàng)建的存儲(chǔ)空間(kmalloc_cache_size[i].cache_pool)是否還有空閑？
很明顯，當(dāng)只有靜態(tài)存儲(chǔ)空間時(shí)，全部的list都只有一個(gè)元素，那就是靜態(tài)創(chuàng)建的Slab

    if(kmalloc_cache_size[i].total_free != 0)
    {
        do
        {
            if(slab->free_count == 0)
                slab = container_of(list_next(&slab->list),struct Slab,list);
            else
                break;
        }while(slab != kmalloc_cache_size[i].cache_pool);   
    }


2.2 存儲(chǔ)空間不夠時(shí)，進(jìn)入else { }，申請(qǐng)分配動(dòng)態(tài)空間
    else
    {
        slab = kmalloc_create(kmalloc_cache_size[i].size);
        
        if(slab == NULL)
        {
            color_printk(BLUE,BLACK,"kmalloc()->kmalloc_create()=>slab == NULL\n");
            return NULL;
        }
        
        kmalloc_cache_size[i].total_free += slab->color_count;

        color_printk(BLUE,BLACK,"kmalloc()->kmalloc_create()<=size:%#010x\n",kmalloc_cache_size[i].size);///////
        
        list_add_to_before(&kmalloc_cache_size[i].cache_pool->list,&slab->list);
    }

3、如果有空閑slab->free_count != 0 就設(shè)置位圖、修改對(duì)應(yīng)參數(shù)
for(j = 0;j < slab->color_count;j++)
    {
        if(*(slab->color_map + (j >> 6)) == 0xffffffffffffffffUL)
        {
            j += 63;
            continue;
        }
            
        if( (*(slab->color_map + (j >> 6)) & (1UL << (j % 64))) == 0 )
        {
            *(slab->color_map + (j >> 6)) |= 1UL << (j % 64);
            slab->using_count++;
            slab->free_count--;

            kmalloc_cache_size[i].total_free--;
            kmalloc_cache_size[i].total_using++;

            return (void *)((char *)slab->Vaddress + kmalloc_cache_size[i].size * j);
        }

}
  • 位圖的修改原理參見

[C語言]模擬color_map位圖分配
http://www.itdecent.cn/p/b4ab98c3d837

kmalloc_create() 函數(shù)的結(jié)構(gòu)

struct Slab * kmalloc_create(unsigned long size)
{
    
       1、申請(qǐng)一張2MB的物理頁
    page = alloc_pages(ZONE_NORMAL,1, 0);
    page_init(page,PG_Kernel);

    switch(size)
    {
        ////////////////////slab + map in 2M page

        case 32:
        case 64:
        case 128:
        case 256:
        case 512:

分支一：
            三個(gè)部分全都放在這張page里面！
        ///////////////////kmalloc slab and map,not in 2M page anymore

        case 1024:      //1KB
        case 2048:
        case 4096:      //4KB
        case 8192:
        case 16384:

        //////////////////color_map is a very short buffer.

        case 32768:
        case 65536:
        case 131072:        //128KB
        case 262144:
        case 524288:
        case 1048576:       //1MB

分支二：
            這張page完全用于內(nèi)存分配 
            管理用的 slab 結(jié)構(gòu)體 以及 color_map 放在其他內(nèi)存池（其他物理頁中）

        default:
            return NULL;
    }   
    
    return slab;
}

分支零：從靜態(tài)存儲(chǔ)空間直接分配內(nèi)存對(duì)象

分支零：從靜態(tài)存儲(chǔ)空間直接分配內(nèi)存對(duì)象.png
  • kmalloc(50) ：50 <= 64 && 50 > 32 選中內(nèi)存池[1] 申請(qǐng)到64b字節(jié)
  • kmalloc(64) ：64 <= 64 && 64 > 32 選中內(nèi)存池[1] 申請(qǐng)到64b字節(jié)
  • kmalloc(600) ：600 <= 1024 && 600 > 512 選中內(nèi)存池[5] 申請(qǐng)到1024b字節(jié)
  • kmalloc(800) ：800 <= 1024 && 800 > 512 選中內(nèi)存池[5] 申請(qǐng)到1024b字節(jié)
  • kmalloc(1020) ：1024 <= 1024 && 1024 > 512 選中內(nèi)存池[5] 申請(qǐng)到1024b字節(jié)

分支一：存儲(chǔ)空間不夠了，申請(qǐng)者一次需要<=512B 的內(nèi)存；

分支一：存儲(chǔ)空間不夠了，申請(qǐng)者一次需要<=512B 的內(nèi)存；

1、假設(shè)我需要申請(qǐng)一塊200字節(jié)的內(nèi)存空間，首先會(huì)找到容量>= 200字節(jié)最小的內(nèi)存池Kmalloc_cache_size[3]，這個(gè)內(nèi)存池的size是256,size是指每次分配的大小，不是什么數(shù)組長(zhǎng)度；
2、然后，在這個(gè)內(nèi)存池的slab鏈表中尋找free_count !=0的slab結(jié)構(gòu)
3、此時(shí)，每個(gè)slab相當(dāng)于管理著一張2MB大小的物理頁，總共有三個(gè)部分：

  • 頭部是存儲(chǔ)空間（用來滿足分配內(nèi)存的需要）；
  • 中間是slab結(jié)構(gòu)體（其中list字段的prev以及next指針可以連接到鏈表中的下一個(gè)slab結(jié)構(gòu)體的list字段，這兩個(gè)指針實(shí)現(xiàn)著鏈表結(jié)構(gòu)）；
  • 尾部是用free_count個(gè)unsigned long變量組成的color_map（這張位圖的每一位都與頭部的存儲(chǔ)空間每size字節(jié)的分配情況一一對(duì)應(yīng)）；

4、雖然這里我們只申請(qǐng)200字節(jié)的空間，但是實(shí)際分配的時(shí)候是按照內(nèi)存池的size進(jìn)行分配的， 也就是申請(qǐng)200字節(jié)，實(shí)際上會(huì)給size=256字節(jié)
5、假設(shè)鏈表的第一個(gè)slab管理著的物理空間其字段free_count!=0，那么就在這張物理頁的存儲(chǔ)空間分配256字節(jié)給申請(qǐng)者，同時(shí)在對(duì)應(yīng)位圖的對(duì)應(yīng)bit上置1，表示分配調(diào)一個(gè)size=256字節(jié)的空間

  • 問：假設(shè)我們申請(qǐng)了很多次，每次都是申請(qǐng)200字節(jié)，那么對(duì)應(yīng)于size=256的slab鏈表上的已有slab們的存儲(chǔ)空間都被填滿之后，這時(shí)候如何還要繼續(xù)申請(qǐng)的還是200字節(jié)的空間會(huì)怎么樣？

答：會(huì)增加一個(gè)新的slab結(jié)構(gòu)，并被鏈接到屬于size=256的slab鏈表上去。
（1）所謂新增的slab結(jié)構(gòu)不僅僅是struct Slab，而其實(shí)是新申請(qǐng)了一整張2MB物理頁（頭部+中間+尾部），用list字段做鏈表連接；
（2）可以看見，這個(gè)新增的slab結(jié)構(gòu)可以再滿足很多次對(duì)于200字節(jié)的申請(qǐng)，因?yàn)榇鎯?chǔ)空間即便是以256字節(jié)作為分割單位來一次次分配，也是可以分很多次的，不要混淆成，每申請(qǐng)一次200字節(jié)，就要?jiǎng)?chuàng)建一個(gè)新的slab結(jié)構(gòu)；
（3）并且只要申請(qǐng)的是200字節(jié)，就是一定在Kmalloc_cache_size[3].size = 256這個(gè)內(nèi)存池里找，如果人家鏈表已有的slab結(jié)構(gòu)的存儲(chǔ)空間都分掉了，就需要在這個(gè)內(nèi)存池的鏈表增加結(jié)點(diǎn)，不會(huì)無緣無故跑去其他內(nèi)存池，比如不會(huì)無緣無故跑去size=32字節(jié)的內(nèi)存池，因?yàn)?code>256就是剛剛好第一個(gè)比200大的數(shù)字，可以滿足申請(qǐng)需求，也就是為了提高物理頁的利用率才搞了那么多不同大小的內(nèi)存池。

分支二：存儲(chǔ)空間不夠了，申請(qǐng)者一次需要>512B & <= 1MB的內(nèi)存；

  • 需要將struct Slab以及color_map與存儲(chǔ)空間分開放，即不能放在同一張屋物理頁里面；

  • struct Slab 大小是72字節(jié)，固定會(huì)選中內(nèi)存池[2].size=128

  • color_map 最大不過是32字節(jié)，固定會(huì)選中內(nèi)存池[0].size=32

  • 具體分配時(shí)有很多種情況，需要看：

32字節(jié)的內(nèi)存池靜態(tài)空間 有空閑 還是 滿？
128字節(jié)的內(nèi)存靜態(tài)空間 有空閑 還是 滿？
帶申請(qǐng)的size是 <=512 還是 > 512 <=1MB ?
待申請(qǐng)的size選中的那個(gè)內(nèi)存池的靜態(tài)空間時(shí) 有空閑 還是 滿？

以下舉兩個(gè)情況的例子：

情況一：靜態(tài)空間可以存放 struct Slab以及color_map

情況一：靜態(tài)空間可以存放 struct Slab以及color_map

只不過這里直接用了靜態(tài)存儲(chǔ)空間來放struct Slab以及color_map
并且新申請(qǐng)到的一整張物理頁全部拿來當(dāng)存儲(chǔ)空間

情況二：在動(dòng)態(tài)空間存放 struct Slab以及color_map


情況二：在動(dòng)態(tài)空間存放 struct Slab以及color_map

struct Slab以及color_map 全部放在動(dòng)態(tài)空間里
仍舊是申請(qǐng)了一張新的物理頁來全部當(dāng)存儲(chǔ)空間

  • 以前，在申請(qǐng)的內(nèi)存比較少時(shí)，是把用于實(shí)際分配空間的存儲(chǔ)空間、管理分配情況的slab結(jié)構(gòu)體以及color_map位圖這三部分都放在同一張物理頁里面；
  • 考慮，最極端的情況，申請(qǐng)1MB的內(nèi)存，如果仍舊把三個(gè)部分都放在一張物理頁里面，那么這張物理頁的存儲(chǔ)空間部分就只能滿足一次申請(qǐng)需要，會(huì)造成內(nèi)存的巨大浪費(fèi)；
  • 因此，在一次申請(qǐng)的字節(jié)數(shù) > 512 且 <= 1MB這種情況下，會(huì)把slab結(jié)構(gòu)體以及color_map位圖拿出來
    1、首先，slab結(jié)構(gòu)體的大小是固定的72字節(jié)，它會(huì)被放到size=128字節(jié)的內(nèi)存池中；
    2、其次，color_map位圖雖然大小不確定，但是由于是申請(qǐng)比較大的空間，color_map位圖不會(huì)太大的，如果是申請(qǐng)1MB，那么color_map位圖其實(shí)只需要一個(gè)unsigned long變量就足夠了，它會(huì)被放到size=32字節(jié)的內(nèi)存池中；
    3、最后，一張完整的2MB大小的物理頁，全部都作為存儲(chǔ)空間，全部可以用來做分配，剛好可以滿足兩次都是1MB的申請(qǐng)需要，內(nèi)存利用率非常高。

三、kfree()

unsigned long kfree(void * address)
{
    int i;
    int index;
    struct Slab * slab = NULL;

1、計(jì)算出待釋放的內(nèi)存對(duì)象所在的物理頁的線性地址
    void * page_base_address = (void *)((unsigned long)address & PAGE_2M_MASK);

    for(i = 0;i < 16;i++)
    {
        slab = kmalloc_cache_size[i].cache_pool;
        do
        {

2、找到管理這個(gè)物理頁（存儲(chǔ)空間）的slab結(jié)構(gòu)體
            if(slab->Vaddress == page_base_address)
            {
3、計(jì)算待釋放的內(nèi)存對(duì)象是存儲(chǔ)空間的第幾個(gè)分配項(xiàng)
                index = (address - slab->Vaddress) / kmalloc_cache_size[i].size;

4、位圖對(duì)應(yīng)bit置 0 
                *(slab->color_map + (index >> 6)) ^= 1UL << index % 64;
5、更新相關(guān)參數(shù)
                slab->free_count++;
                slab->using_count--;

                kmalloc_cache_size[i].total_free++;
                kmalloc_cache_size[i].total_using--;

6、如果本次釋放導(dǎo)致，管理該存儲(chǔ)空間全部被釋放了，
看內(nèi)存池剩余空閑空間是否滿足kmalloc_cache_size[i].total_free >= slab->color_count * 3 / 2，
并且當(dāng)前slab是管理動(dòng)態(tài)存儲(chǔ)空間的slab，而不是管理靜態(tài)存儲(chǔ)空間的slab，就再釋放這個(gè)slab結(jié)構(gòu)體
                if((slab->using_count == 0) && (kmalloc_cache_size[i].total_free >= slab->color_count * 3 / 2) && (kmalloc_cache_size[i].cache_pool != slab))
                {
                    switch(kmalloc_cache_size[i].size)
                    {
                        ////////////////////slab + map in 2M page
應(yīng)對(duì)分支一：              
                        case 32:
                        case 64:
                        case 128:
                        case 256:   
                        case 512:
                            list_del(&slab->list);
                            kmalloc_cache_size[i].total_free -= slab->color_count;

                            page_clean(slab->page);
                            free_pages(slab->page,1);
                            break;
應(yīng)對(duì)分支二：                      
                        default:
                            list_del(&slab->list);
                            kmalloc_cache_size[i].total_free -= slab->color_count;
    
                            kfree(slab->color_map);

                            page_clean(slab->page);
                            free_pages(slab->page,1);
                            kfree(slab);
                            break;
                    }
 
                }

                return 1;
            }
            else
                slab = container_of(list_next(&slab->list),struct Slab,list);               

        }while(slab != kmalloc_cache_size[i].cache_pool);
    
    }
    
    color_printk(RED,BLACK,"kfree() ERROR: can`t free memory\n");
    
    return 0;
}
  • 應(yīng)對(duì)分支二這里，有兩句非常妙的調(diào)用 kfree(slab->color_map); 以及 kfree(slab);，因?yàn)榉种Фr(shí)，這兩個(gè)部分不和存儲(chǔ)空間處于同一張物理頁，因此需要嵌套調(diào)用kfree，把它們看做是一個(gè)內(nèi)存對(duì)象去釋放，參見分支二的兩張圖示，這兩個(gè)部分所占用的存儲(chǔ)空間被釋放后，管理這兩處存儲(chǔ)空間的slab以及color_map同樣會(huì)更新；
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 第八章 內(nèi)存管理 本章通過三部分內(nèi)容描述內(nèi)核給自己動(dòng)態(tài)分配內(nèi)存： ...
    rlkbk閱讀 526評(píng)論 0贊 1
  • Linux 內(nèi)存管理 1 頁的概念 linux 內(nèi)核中把物理頁作為內(nèi)存分配的最小單位，32位CPU 頁的大小通常為...
    赤兔歡閱讀 3,420評(píng)論 0贊 5
  • Swift1> Swift和OC的區(qū)別1.1> Swift沒有地址/指針的概念1.2> 泛型1.3> 類型嚴(yán)謹(jǐn) 對(duì)...
    cosWriter閱讀 11,671評(píng)論 1贊 32
  • linux 內(nèi)存是所有從事相關(guān)技術(shù)人員，需要深入了解的計(jì)算機(jī)資源管理方法論，合理的使用內(nèi)存，有助于提升機(jī)器的性能和...
    Leon_Geo閱讀 1,379評(píng)論 0贊 22
  • 1、Linux內(nèi)存頁管理 Linux內(nèi)核管理物理內(nèi)存是通過分頁機(jī)制實(shí)現(xiàn)的，它將整個(gè)內(nèi)存劃分成4K大小頁，作為使分配...
    gbmaotai閱讀 1,531評(píng)論 0贊 2

友情鏈接更多精彩內(nèi)容