內(nèi)核sanitize_e820_map函數(shù)詳解(征服內(nèi)存管理模塊的起點(diǎn))

cluter

原理：
bios探測(cè)到的內(nèi)存段信息可能是以下的情況，內(nèi)核需要重新整理內(nèi)存段信息：
*        Sample memory map (w/overlaps):
*           ____22__________________
*           ______________________4_
*           ____1111________________
*           _44_____________________
*           11111111________________
*           ____________________33__
*           ___________44___________
*           __________33333_________
*           ______________22________
*           ___________________2222_
*           _________111111111______
*           _____________________11_
*           _________________4______
*

整理后的內(nèi)存段信息應(yīng)該如下：
*        Sanitized equivalent (no overlap):
*           1_______________________
*           _44_____________________
*           ___1____________________
*           ____22__________________
*           ______11________________
*           _________1______________
*           __________3_____________
*           ___________44___________
*           _____________33_________
*           _______________2________
*           ________________1_______
*           _________________4______
*           ___________________2____
*           ____________________33__
*           ______________________4_

所以sanitize_e820_map的主要功能還是內(nèi)存段排序，還有就是對(duì)于重疊的內(nèi)存段的處理如下：

111111---內(nèi)存段類(lèi)型1
  333   ---內(nèi)存段類(lèi)型3

由于333的內(nèi)存類(lèi)型為3 大于內(nèi)存類(lèi)型1，所以覆蓋后內(nèi)存如下：
133311

//下面的函數(shù)只介紹核心的幾個(gè)處理過(guò)程:
假設(shè)Bios探測(cè)到的內(nèi)存信息如下：
        333
1111111111111
    22222222

int __init sanitize_e820_map(struct e820entry *biosmap, int max_nr_map,
                             u32 *pnr_map)
{

       
        //記錄內(nèi)存段的改變點(diǎn):即每個(gè)內(nèi)存段的(開(kāi)始地址:結(jié)束地址)
        chgidx = 0;
        for (i = 0; i < old_nr; i++)        {
                if (biosmap.size != 0) {
                        //開(kāi)始地址              
                        change_point[chgidx]->addr = biosmap.addr;
                        change_point[chgidx++]->pbios = &biosmap;
                        //結(jié)束地址
                        change_point[chgidx]->addr = biosmap.addr +
                                biosmap.size;
                        change_point[chgidx++]->pbios = &biosmap;
                }
        }
        chg_nr = chgidx;

        //然后就是排列這些內(nèi)存的change point,順序由低到高
        //下面的排序過(guò)程感覺(jué)像 “冒泡排序”,但是好像不如冒泡排序
        //排序原理：每次掃描，把最大的地址(change point)排列到數(shù)組最后。
         
        still_changing = 1;
        while (still_changing)        {
                still_changing = 0;
                for (i = 1; i < chg_nr; i++)  {
                        unsigned long long curaddr, lastaddr;
                        unsigned long long curpbaddr, lastpbaddr;

                        curaddr = change_point->addr;
                        lastaddr = change_point[i - 1]->addr;
                        curpbaddr = change_point->pbios->addr;
                        lastpbaddr = change_point[i - 1]->pbios->addr;

                        /*
                         * swap entries, when:
                         *
                         * curaddr > lastaddr or
                         * curaddr == lastaddr and curaddr == curpbaddr and
                         * lastaddr != lastpbaddr
                         */
                        //1:當(dāng)前地址 <   上一個(gè)地址  交換
                        //2:當(dāng)前地址 == 上一個(gè)地址  && 當(dāng)前地址為內(nèi)存段的開(kāi)始地址 而 上一地址不是內(nèi)存段開(kāi)始地址 則也要交換
                        if (curaddr < lastaddr ||
                            (curaddr == lastaddr && curaddr == curpbaddr &&
                             lastaddr != lastpbaddr)) {
                                change_tmp = change_point;
                                change_point = change_point[i-1];
                                change_point[i-1] = change_tmp;
                                still_changing = 1;
                        }
                }
        }

//當(dāng)整個(gè)循環(huán)處理完內(nèi)存排序應(yīng)該如下:
      
1111111111111
    22222222
      333

//即change_point的數(shù)組應(yīng)該如下:

1SA|2SA|3SA|3EA|2EA|1EA  (SA==start address         EA==end address)

cluter

/* 創(chuàng)建一個(gè)新的Bios影射表 */
        overlap_entries = 0;         /* number of entries in the overlap table */
        new_bios_entry = 0;         /* index for creating new bios map entries */
        last_type = 0;                 /* start with undefined memory type */
        last_addr = 0;                 /* start with 0 as last starting address */


        for (chgidx = 0; chgidx < chg_nr; chgidx++) {
                /* keep track of all overlapping bios entries */
                //英文的意思是：記錄所有覆蓋的bios項(xiàng)
                //即如果 change_point的地址==該內(nèi)存項(xiàng)的開(kāi)始地址
                //也就是說(shuō)：

1111111111111
    22222222
      333

從1SA開(kāi)始--2SA--3SA都認(rèn)為是有內(nèi)存覆蓋的，因?yàn)橐粋�(gè)內(nèi)存項(xiàng)還沒(méi)結(jié)束，下一個(gè)內(nèi)存項(xiàng)就開(kāi)始了，想想也是存在內(nèi)存覆蓋的。
               
                if (change_point[chgidx]->addr ==
                    change_point[chgidx]->pbios->addr) {
                        /*
                         * add map entry to overlap list (> 1 entry
                         * implies an overlap)
                         */
                         //所以要記錄下來(lái)：所以覆蓋鏈表：1SA--2SA--3SA
                        overlap_list[overlap_entries++] =
                                change_point[chgidx]->pbios;
                } else {
                        直到3EA，即有一個(gè)內(nèi)存段結(jié)束了。
                        /*
                         * remove entry from list (order independent,
                         * so swap with last)
                         */
                         //下面的處理是：當(dāng)遇到 3EA，就把3SA從鏈表中刪除
                         //原理應(yīng)該是:當(dāng)一項(xiàng)結(jié)束時(shí)，該項(xiàng)就從覆蓋聊表中刪除，我想個(gè)也好理解。
即  當(dāng)覆蓋情況是
1111111111111
    22222222
      333
遇到3EA時(shí)，就該處理下面的覆蓋情況:
1111111111111
    22222222
即從原先的覆蓋鏈表中刪除內(nèi)存類(lèi)型為3的項(xiàng)。


                        for (i = 0; i < overlap_entries; i++) {
                                if (overlap_list[i] ==
                                    change_point[chgidx]->pbios)
                                        overlap_list[i] =
                                                overlap_list[overlap_entries-1];
                        }
                        overlap_entries--;
                }
                /*
                 * if there are overlapping entries, decide which
                 * "type" to use (larger value takes precedence --
                 * 1=usable, 2,3,4,4+=unusable)
                 */
                //從覆蓋鏈表中選出內(nèi)存類(lèi)型最大的作為當(dāng)前類(lèi)型
                current_type = 0;
                for (i = 0; i < overlap_entries; i++)
                        if (overlap_list[i]->type > current_type)
                                current_type = overlap_list[i]->type;
                /*
                 * continue building up new bios map based on this
                 * information
                 */
                //當(dāng)前type和原先的type不同時(shí)，必須要新建一個(gè)Bios entry
                if (current_type != last_type)        {
                           //0type應(yīng)該認(rèn)為是該段內(nèi)存沒(méi)有被使用
                            if (last_type != 0)         {
                                //上一entry的內(nèi)存段大小 由此可得
                                new_bios[new_bios_entry].size =change_point[chgidx]->addr - last_addr;
                                //遞增bios的entry項(xiàng)
                                if (new_bios[new_bios_entry].size != 0)
                                        if (++new_bios_entry >= max_nr_map)
                                                break;
                        }
                        if (current_type != 0)        {
                                new_bios[new_bios_entry].addr =
                                        change_point[chgidx]->addr; //新建entry的開(kāi)始地址
                                new_bios[new_bios_entry].type = current_type; //新建entry的類(lèi)型
                                last_addr = change_point[chgidx]->addr;
                        }
                        last_type = current_type;//使上一類(lèi)型為當(dāng)前類(lèi)型
                }
        }
       
        new_nr = new_bios_entry;

       
        memcpy(biosmap, new_bios, new_nr * sizeof(struct e820entry));
        *pnr_map = new_nr;

        return 0;
}

cluter

假設(shè)內(nèi)存信息排序后如下：
1111111111111
    22222222
      333

即change point數(shù)組如下:

1SA|2SA|3SA|3EA|2EA|1EA

那么處理內(nèi)存覆蓋函數(shù)的流程如下:

循環(huán)1：

1SA加入 overlap_list:即overlap_list==1SA
current type = 1
新建一個(gè)內(nèi)存段,并設(shè)置(開(kāi)始地址為0,類(lèi)型為1)

循環(huán)2:

2SA加入 overlap_list:即overlap_list==1SA,2SA
current type=2
設(shè)置上一個(gè)內(nèi)存段的大小為2===>bios[0]=(開(kāi)始地址0，大小2，類(lèi)型1)
新建一個(gè)內(nèi)存段,并設(shè)置(開(kāi)始地址為2,類(lèi)型為2)

循環(huán)3：

3SA加入overlap_list:即overlap_list==1SA,2SA,3SA
current type=3
設(shè)置上一個(gè)內(nèi)存段的大小為1
新建一個(gè)內(nèi)存段,并設(shè)置(開(kāi)始地址為3,類(lèi)型為3)====>bios[1]=(開(kāi)始地址2，大小1，類(lèi)型2)

循環(huán)4:

類(lèi)存類(lèi)型為3的從overlap_list中刪除:即overlap_list==1SA,2SA
current type=2
設(shè)置上一個(gè)內(nèi)存段的大小為3====>bios[2]=(開(kāi)始地址3，大小3，類(lèi)型2)
新建一個(gè)內(nèi)存段,并設(shè)置(開(kāi)始地址為6,類(lèi)型為2)

循環(huán)5:

類(lèi)存類(lèi)型為2的從overlap_list中刪除:即overlap_list==1SA
current type=1
設(shè)置上一個(gè)內(nèi)存段的大小為4====>bios[3]=(開(kāi)始地址6，大小4，類(lèi)型2)
新建一個(gè)內(nèi)存段,并設(shè)置(開(kāi)始地址為10,類(lèi)型為1)

循環(huán)6:

類(lèi)存類(lèi)型為1的從overlap_list中刪除:即overlap_list==NULL
current type=0
設(shè)置上一個(gè)內(nèi)存段的大小為3====>bios[4]=(開(kāi)始地址10，大小3，類(lèi)型1)

所以?xún)?nèi)存覆蓋處理后的結(jié)果為:
1                  111
    2      2222
      333

amarant

這123是什么意思�。壳懊娴膱D是表示什么？

cluter

回復(fù) 4# amarant


    123表示內(nèi)存類(lèi)型啊     比如 111 表示這塊內(nèi)存區(qū)是usable內(nèi)存  2222可能是reserved口用的  3333表示ACPI data等等。

連續(xù)的數(shù)字表示內(nèi)存區(qū)，具體的數(shù)字大小表示內(nèi)存區(qū)的類(lèi)型。

amarant

回復(fù) 5# cluter


    看得出這是一個(gè)好貼，只是現(xiàn)在還沒(méi)看過(guò)e820的東東（看了基本內(nèi)核的書(shū)都沒(méi)有講。。），有時(shí)間琢磨琢磨

cluter

回復(fù) 6# amarant


    謝謝哈，恩，這個(gè)我也費(fèi)了些力氣才弄明白。最近研究?jī)?nèi)存管理模塊，這個(gè)是內(nèi)存管理的開(kāi)始吧(當(dāng)然啟動(dòng)項(xiàng)會(huì)有原始頁(yè)表的初始化)，所以弄明白還是很有用的。。。

accessory

不錯(cuò)。 關(guān)于E820，可以看看下面這篇文檔：
http://wiki.osdev.org/Detecting_Memory_%28x86%29

amarant

那我今天就看看e820是怎么回事，

dingyujie

大牛！最近剛看這里，這個(gè)函數(shù)費(fèi)了很大勁也沒(méi)怎么看明了，經(jīng)過(guò)樓主指點(diǎn)，算是明白了。謝謝