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

原理：
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---内存段类型A
  333   ---内存段类型B

由于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[i].size != 0) {
                        //开始地址              
                        change_point[chgidx]->addr = biosmap[i].addr;
                        change_point[chgidx++]->pbios = &biosmap[i];
                        //结束地址
                        change_point[chgidx]->addr = biosmap[i].addr +
                                biosmap[i].size;
                        change_point[chgidx++]->pbios = &biosmap[i];
                }
        }
        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[i]->addr;
                        lastaddr = change_point[i - 1]->addr;
                        curpbaddr = change_point[i]->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[i];
                                change_point[i] = 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)

/* 创建一个新的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;
}