贝城社区 » 电脑·手机·数码 » Buddy算法认识（草稿）

hujiao 发表于 2006-4-28 16:36

Buddy算法认识（草稿）

Buddy算法认识（草稿）
一、总述
       Buddy（伙伴）算法每次分配包含一个或者多个物理页面的内存块，页面以2的次幂的内存块来分配。首先搜寻满足请求大小的页面，它从满足当前申请大小的Buddy数据结构的m_ freePages域着手沿链来搜索空闲页面。如果没有这样请求大小的空闲页面，则它搜索两倍于请求大小的内存块。这个过程一直将持续到所有的Buddy 被搜索完或找到满足要求的内存块为。如果找到的页面块大于请求的块则对其进行分割以使其大小与请求块匹配。由于块大小都是2的次幂所以分割过程十分简单：空闲块（低地址）被连进相应大小的队列而这个页面块被分配给调用者。 释放时，先检查该块的伙伴的使用情况，如果没有被使用，则合并这对Buddy，再检查该两倍大小的块的Buddy，一直持续到合并后的块没有Buddy为止，并将之链到该大小的freepage队列中。


二、一些数据结构
Zone： 具有不同属性，或不连续的区域
Map： map中的一个位表示相邻的一对内存块（Buddy、伙伴）的使用情况，0表示都没有被使用或都被使用，1表示有其中一块被使用。
Order：表示分配块容量，大小为2^Order个页。

   struct Page {//指示每个页面的状态，组成数组
       Delink  m_link;    //将该页面开始的块链到freepage队列用的数据结构
       ulong   m_flags;  //该页状态
       Zone    * m_pZone; //属于的Zone
   };

   struct Buddy { //各个Order相关的信息
       Delink  m_freePages;   //freepage队列
       void    * m_map;//该Order下的内存块的Buddy情况
   };

   struct Zone {
       page_t  m_start;                  //页起始
       page_t  m_end;
       int     m_apxHighOrder;     //当前Zone可以分配的最大的Order
       size_t  m_nFreePages;       //当前Zone的freepage数量
       Buddy   m_buddies[MAX_ORDER]; //各个Order信息
   };

三、主要函数
初始化：initPages_o、initZone、reclaimPages
申请释放：allocPages、_freePages
//申请pages数组并初始化每个页的信息。
INIT_CODE static bool initPages_o(const Region * zones, size_t nZones,
                               Region * pFree, size_t * appendCnt)
{
   // virtual page frame range
   Region vr;
   vr.start = (page_t)-1;
   vr.end = 0;

//所有页面的总数
   for (size_t i = 0; i < BSP::memZoneCount; i++) {
       vr.start = min(BSP::memZones[i].start, vr.start);
       vr.end   = max(BSP::memZones[i].end, vr.end);
   }

   #define EFFECTIVE   (STAT_GET(memTotal) >> PAGE_SHIFT)
   dprintf(("0x%x effective, 0x%x illusive page frames\n", EFFECTIVE,
       vr.end - vr.start - EFFECTIVE));

//申请pages数组内存
   g_pages = (Page *)staticAlloc_n(sizeof(Page) * (vr.end - vr.start));
   if (!g_pages) return false;

//使以后访问数组时，下标和内存地址一致
   g_pages = g_pages - vr.start;

   size_t current = 0;
   page_t i;

   // zones has been sorted. we must get the real index of the
   // current zone in BSP::memZones.
   //
   Zone * realZone = findZone(zones);

//初始化每个page结构
   for (i = vr.start; i < vr.end; i++) {

       if (i >= zones[current].end) {
           current++;
           assert(current < nZones);
           realZone = findZone(zones + current);
       }

       g_pages[i].m_link.init();

       if (i < zones[current].start) {
           // it's an illusive page
           g_pages[i].m_flags  = PGF_ILLUSIVE;
           g_pages[i].m_pZone  = 0;

       } else {
           // it's a effective page. mark all effective pages
           // as reserved
           g_pages[i].m_flags  = PGF_RESERVED;
           g_pages[i].m_pZone  = realZone;
       }
   }

   // append to free list illusive page structures.
   *appendCnt = 0;

   for (i = 1; i < nZones; i++) {
       if (setFreeRegion(pFree + *appendCnt,
               roundUp(PA(g_pages + zones[i - 1].end), PAGE_SIZE) >> PAGE_SHIFT,
               PA(g_pages + zones[i].start) >> PAGE_SHIFT)) {
           (*appendCnt)++;
       }
   }

   return true;
}

//申请每个order下的map数组、初始化。
INIT_CODE bool initZone(Zone * z, const Region * r)
{
   z->m_start = r->start;
   z->m_end   = r->end;
   z->m_apxHighOrder = -1;
   z->m_nFreePages = 0;

   size_t mapBit = r->end - r->start;
   size_t mapByte;

//申请各个order下map内存，需要的map bit为：总page数>>(1+order);
   for (int i = 0; i < MAX_ORDER; i++) {
       z->m_buddies[i].m_freePages.init();

       mapBit  = roundUp(mapBit, 2) >> 1;
       mapByte = roundUp(mapBit,  >> 3;

       z->m_buddies[i].m_map = staticAlloc_n(mapByte);
       if (!z->m_buddies[i].m_map) return false;
       memset(z->m_buddies[i].m_map, 0, mapByte);
   }
   return true;
}


//重新收回该范围内的页面
bool reclaimPages(page_t start, page_t end)
{
   assert(isValidPage(start) && isValidPage(end));

   Zone * z = g_pages[start].m_pZone;

   for (page_t i = start; i < end; i++) {
       if (!(g_pages[i].m_flags & PGF_RESERVED)) {
           dprintf(("error: try to reclaim non-reserved page %08x.\n",
               i << PAGE_SHIFT));
           return false;
       }
       if (g_pages[i].m_pZone != z) {
           dprintf(("error: try to reclaim page %08 across zones.\n",
               i << PAGE_SHIFT));
           return false;
       }
       assert(!(g_pages[i].m_flags & PGF_ILLUSIVE));
       assert(i >= z->m_start && i < z->m_end);
       g_pages[i].m_flags &= ~PGF_RESERVED;
       SET_PAGE_FREE(g_pages[i], false);
   }
   start -= z->m_start;
   end   -= z->m_start;
   assert(start >= 0 && end >= 0);

restartLoop:
   while (start < end) {
       int order = MAX_ORDER;
       ulong mask;

//找出该块内存中的可以拆分的最大order，并free，反复
       while (order--) {           mask = (~0UL) << order;
           if (!(start & ~mask)) {
               while (1) {
                  if (start - mask <= end) {
                       _freePages(start + z->m_start, order);
                       start += -mask;
                       assert(start <= end);
                       goto restartLoop;
                   } else {
                       order--;
                       mask = (~0UL) << order;
                   }
               }
               UNREACHABLE;
           }
       }
       UNREACHABLE;
   }
   return true;
}


//申请2^order大小的页块
address allocPages(int order, uint zonePrefer)
{
   assert(order >= 0);
   assert(zonePrefer < BSP::memZoneCount);
   Zone * z = g_zones + zonePrefer;

restart:
   while (unlikely(z->m_apxHighOrder < order)) {//如果当前Zone可以分配的最大order不够，换个zone
       if (--z < g_zones) {
           puts("fatal: physical memory overflow"
               " or request block too large\n");
           return 0;
       }
       dprintf(("buddy: zone %d overflow, turn to next zone.\n",
           z - g_zones + 1));
   }

   Buddy * buddy = z->m_buddies + order; //找到该order的buddy数据结构
   Page * p;
   int newOrder = order;

   do {
       if (!buddy->m_freePages.empty()) {//该order的freepage链表中有空闲
           p = mem2obj(buddy->m_freePages.next(), Page, m_link);
           goto found;
       }
       newOrder++;//没有，则往两倍于该大小的链表中查找
       buddy++;
   } while (newOrder < MAX_ORDER);

   dprintf(("buddy: high order miss. zone %d high order %d order %d\n",
       z - g_zones, z->m_apxHighOrder, order));

   // approximate highest order greater than actual highest order,
   // (i.e. high order miss). we must adjust and restart.
//
//如果到最大order还没找到，则该zone的可以分配最大order（apxHighOrder）有问题，设置apxHighOrder（不一定是正确值），换zone
   z->m_apxHighOrder = order - 1;
   goto restart;

found:
   assert(newOrder < MAX_ORDER);
   assert(newOrder <= z->m_apxHighOrder);

   // for debug only
   // note: the whole loop will be optimized away on release build
   //
   Page * i;
   for (i = p; i < p + (1 << newOrder); i++) {
       assert(!(i->m_flags & (PGF_ILLUSIVE | PGF_RESERVED)));
       assert(IS_PAGE_FREE(*i));
   }

   // update approximate highest order if necessary
//
//如果最大的可分配的块被申请，并freepage链表为空
   if (z->m_apxHighOrder == newOrder &&
           p->m_link.next() == &buddy->m_freePages) {
       z->m_apxHighOrder = newOrder - 1;
   }
   p->m_link.partialDetach();
   page_t index = p - (g_pages + z->m_start); //在pages数组中的索引

   changeBit(buddy->m_map, index >> (1 + newOrder)); //更改该对buddy的              //map bit

   page_t size = 1 << newOrder;
//如果是从大于申请大小的块中分配的
   while (newOrder > order) {
       buddy--;
       newOrder--;
       size >>= 1;

       assert(buddy - z->m_buddies >= 0);
       assert(size >= (1U << order));
//将剩下的块拆分，并挂到相应的freepage链表中，置map bit位
       buddy->m_freePages.addNext(&p->m_link);
       changeBit(buddy->m_map, index >> (1 + newOrder));

       index += size;
       p += size;
   }

   assert(size == (1U << order));

   // for debug only
   for (i = p; i < p + (1 << order); i++) {
       SET_PAGE_FREE(*i, false);
   }

   z->m_nFreePages -= size;

   return (p - g_pages) << PAGE_SHIFT;

}
//从start释放2^order页的块
void _freePages(page_t start, int order)
{
   assert(isValidPage(start));
   assert(0 <= order < MAX_ORDER);

   ulong mask = (~0UL) << order;
   Zone * z = g_pages[start].m_pZone;

   assert(start >= z->m_start);
   assert(start - mask <= z->m_end);

   page_t base = z->m_start;
   z->m_nFreePages -= mask; //总free’s page数加2^order
   start -= base;  //在pages中的索引
   assert((start & mask) == start);

   // for debug only
   // note: the whole loop will be optimized away on release build
   //
   page_t i;
   for (i = start + base; i < start + base - mask; i++) {
       assert(!(g_pages[i].m_flags & (PGF_ILLUSIVE | PGF_RESERVED)));
       assert(!IS_PAGE_FREE(g_pages[i]));
       SET_PAGE_FREE(g_pages[i], true);
   }

   Buddy * buddy = z->m_buddies + order;
   page_t index = start >> (1 + order);

//当mask所遮掩的位长为(MAX_ORDER-1)时,和恰好为零,即达到了最大块指数
   while (mask + (1 << (MAX_ORDER - 1))) {
       assert(buddy - z->m_buddies < MAX_ORDER);
//如果它的buddy是空闲的
       if (!testChangeBit(buddy->m_map, index)) break;

       // move the buddy off from the free list if it's free.
       //
       for (i = 0; i < -mask; i++) {
           assert(IS_PAGE_FREE(g_pages[base + (start ^ -mask) + i]));
       }
//将它的buddy从free page链表中摘除
       g_pages[base + (start ^ -mask)].m_link.partialDetach();

//往更高一级order在检查buddy情况
       mask <<= 1;
       index >>= 1;
       buddy++;
       start &= mask;
   }
//将合并后的整个大块加到该大小的free page链表中
buddy->m_freePages.addNext(&g_pages[start + base].m_link);
     //如果合并后的块order比该zone可分配的最大order大，则更改之
   if (z->m_apxHighOrder < buddy - z->m_buddies) {
       z->m_apxHighOrder = buddy - z->m_buddies;
   }

smile_hehe 发表于 2006-4-29 00:27

不是原创吧，我记得我在哪看过这个~~~~~

hujiao 发表于 2006-4-30 10:31

[quote]原帖由 [i]smile_hehe[/i] 于 2006-4-29 00:27 发表
不是原创吧，我记得我在哪看过这个~~~~~ [/quote]
当然不是原创了，要知道技术贴没有几个是原创的。就算自己写的，说不定别人早写过了。

smile_hehe 发表于 2006-4-30 23:50

[quote]原帖由 [i]hujiao[/i] 于 2006-4-30 10:31 发表

当然不是原创了，要知道技术贴没有几个是原创的。就算自己写的，说不定别人早写过了。 [/quote]
[em17]看到草稿两个字，又没有加转载相关的文字，本来还以为是你原创的呢，进来看看却发现不是~是我误解了~不过
如果技术贴没有几个是原创的，那它们从哪里来的呢？最初作者难道不是原创？[em16]其实贝壳可以写原创的人很多，我就在网上见过不少贝壳的牛人

hujiao 发表于 2006-5-1 01:10

[quote]原帖由 [i]smile_hehe[/i] 于 2006-4-30 23:50 发表

看到草稿两个字，又没有加转载相关的文字，本来还以为是你原创的呢，进来看看却发现不是~是我误解了~不过
如果技术贴没有几个是原创的，那它们从哪里来的呢？最初作者难道不是原创？其实贝壳可以写原创的人很多 ... [/quote]
我并不是说没有原创，比如linux，除了写他的开源社区的作者，其他人要说 原创就谈不上了，
vc一般的东西在msdn都有了，要原创除非挑出毛病，或者换个例子说明。
可能我对原创理解不同吧。

查看完整版本: Buddy算法认识（草稿）