内核sanitize_e820_map函数详解(征服内存管理模块的起点)

cluter

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

整理后的内存段信息应该如下：
*        Sanitized equivalent (no overlap):
*           1_______________________
*           _44_____________________
*           ___1____________________
*           ____22__________________
*           ______11________________
*           _________1______________
*           __________3_____________
*           ___________44___________
*           _____________33_________
*           _______________2________
*           ________________1_______
*           _________________4______
*           ___________________2____
*           ____________________33__
*           ______________________4_

所以sanitize_e820_map的主要功能还是内存段排序，还有就是对于重叠的内存段的处理如下：

111111---内存段类型1
  333   ---内存段类型3

由于333的内存类型为3 大于内存类型1，所以覆盖后内存如下：
133311

//下面的函数只介绍核心的几个处理过程:
假设Bios探测到的内存信息如下：
        333
1111111111111
    22222222

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

       
        //记录内存段的改变点:即每个内存段的(开始地址:结束地址)
        chgidx = 0;
        for (i = 0; i < old_nr; i++)        {
                if (biosmap.size != 0) {
                        //开始地址              
                        change_point[chgidx]->addr = biosmap.addr;
                        change_point[chgidx++]->pbios = &biosmap;
                        //结束地址
                        change_point[chgidx]->addr = biosmap.addr +
                                biosmap.size;
                        change_point[chgidx++]->pbios = &biosmap;
                }
        }
        chg_nr = chgidx;

        //然后就是排列这些内存的change point,顺序由低到高
        //下面的排序过程感觉像 “冒泡排序”,但是好像不如冒泡排序
        //排序原理：每次扫描，把最大的地址(change point)排列到数组最后。
         
        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:当前地址 <   上一个地址  交换
                        //2:当前地址 == 上一个地址  && 当前地址为内存段的开始地址 而 上一地址不是内存段开始地址 则也要交换
                        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;
                        }
                }
        }

//当整个循环处理完内存排序应该如下:
      
1111111111111
    22222222
      333

//即change_point的数组应该如下:

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

cluter

/* 创建一个新的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项
                //即如果 change_point的地址==该内存项的开始地址
                //也就是说：

1111111111111
    22222222
      333

从1SA开始--2SA--3SA都认为是有内存覆盖的，因为一个内存项还没结束，下一个内存项就开始了，想想也是存在内存覆盖的。
               
                if (change_point[chgidx]->addr ==
                    change_point[chgidx]->pbios->addr) {
                        /*
                         * add map entry to overlap list (> 1 entry
                         * implies an overlap)
                         */
                         //所以要记录下来：所以覆盖链表：1SA--2SA--3SA
                        overlap_list[overlap_entries++] =
                                change_point[chgidx]->pbios;
                } else {
                        直到3EA，即有一个内存段结束了。
                        /*
                         * remove entry from list (order independent,
                         * so swap with last)
                         */
                         //下面的处理是：当遇到 3EA，就把3SA从链表中删除
                         //原理应该是:当一项结束时，该项就从覆盖聊表中删除，我想个也好理解。
即  当覆盖情况是
1111111111111
    22222222
      333
遇到3EA时，就该处理下面的覆盖情况:
1111111111111
    22222222
即从原先的覆盖链表中删除内存类型为3的项。


                        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)
                 */
                //从覆盖链表中选出内存类型最大的作为当前类型
                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
                 */
                //当前type和原先的type不同时，必须要新建一个Bios entry
                if (current_type != last_type)        {
                           //0type应该认为是该段内存没有被使用
                            if (last_type != 0)         {
                                //上一entry的内存段大小 由此可得
                                new_bios[new_bios_entry].size =change_point[chgidx]->addr - last_addr;
                                //递增bios的entry项
                                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的开始地址
                                new_bios[new_bios_entry].type = current_type; //新建entry的类型
                                last_addr = change_point[chgidx]->addr;
                        }
                        last_type = current_type;//使上一类型为当前类型
                }
        }
       
        new_nr = new_bios_entry;

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

        return 0;
}

cluter

假设内存信息排序后如下：
1111111111111
    22222222
      333

即change point数组如下:

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

那么处理内存覆盖函数的流程如下:

循环1：

1SA加入 overlap_list:即overlap_list==1SA
current type = 1
新建一个内存段,并设置(开始地址为0,类型为1)

循环2:

2SA加入 overlap_list:即overlap_list==1SA,2SA
current type=2
设置上一个内存段的大小为2===>bios[0]=(开始地址0，大小2，类型1)
新建一个内存段,并设置(开始地址为2,类型为2)

循环3：

3SA加入overlap_list:即overlap_list==1SA,2SA,3SA
current type=3
设置上一个内存段的大小为1
新建一个内存段,并设置(开始地址为3,类型为3)====>bios[1]=(开始地址2，大小1，类型2)

循环4:

类存类型为3的从overlap_list中删除:即overlap_list==1SA,2SA
current type=2
设置上一个内存段的大小为3====>bios[2]=(开始地址3，大小3，类型2)
新建一个内存段,并设置(开始地址为6,类型为2)

循环5:

类存类型为2的从overlap_list中删除:即overlap_list==1SA
current type=1
设置上一个内存段的大小为4====>bios[3]=(开始地址6，大小4，类型2)
新建一个内存段,并设置(开始地址为10,类型为1)

循环6:

类存类型为1的从overlap_list中删除:即overlap_list==NULL
current type=0
设置上一个内存段的大小为3====>bios[4]=(开始地址10，大小3，类型1)

所以内存覆盖处理后的结果为:
1                  111
    2      2222
      333

amarant

这123是什么意思啊？前面的图是表示什么？

cluter

回复 4# amarant


    123表示内存类型啊     比如 111 表示这块内存区是usable内存  2222可能是reserved口用的  3333表示ACPI data等等。

连续的数字表示内存区，具体的数字大小表示内存区的类型。

amarant

回复 5# cluter


    看得出这是一个好贴，只是现在还没看过e820的东东（看了基本内核的书都没有讲。。），有时间琢磨琢磨

cluter

回复 6# amarant


    谢谢哈，恩，这个我也费了些力气才弄明白。最近研究内存管理模块，这个是内存管理的开始吧(当然启动项会有原始页表的初始化)，所以弄明白还是很有用的。。。

accessory

不错。 关于E820，可以看看下面这篇文档：
http://wiki.osdev.org/Detecting_Memory_%28x86%29

amarant

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

dingyujie

大牛！最近刚看这里，这个函数费了很大劲也没怎么看明了，经过楼主指点，算是明白了。谢谢