同伴系统分析

伙伴系统分析

chipset: MSM8X25Q

Codebase: Android4.1

Kernel: 3.4.0

         关于伙伴系统算法的原理还是比较好理解的，这里不作复数。直接看下关键数据结构。

相关信息可以从/proc/buddyinfo读取到，各个值含义依次为节点号， zone类型，后面的值表示从0阶开始各个阶空闲的页数：
MIGRATE_TYPES是作为反碎片的一种机制，专有名叫迁移类型。大概的原理就是将伙伴系统的内存页分为几种类型，有可移动，不可移动，可回收等，同一类型的页放在一个区域，如不可回收的页不能放在可移动类型区域，这样对可以移动区域，伙伴系统就可以回收了。
__alloc_pages_slowpath():
static inline struct page *__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,struct zonelist *zonelist, enum zone_type high_zoneidx,nodemask_t *nodemask, struct zone *preferred_zone,int migratetype){const gfp_t wait = gfp_mask & __GFP_WAIT;struct page *page = NULL;int alloc_flags;unsigned long pages_reclaimed = 0;unsigned long did_some_progress;bool sync_migration = false;bool deferred_compaction = false;~~sniprestart:/*如果没有禁止内存回收的话就唤醒交换线程来进行内存页面回收, 写回或换出很少使用的页到磁盘上。*/if (!(gfp_mask & __GFP_NO_KSWAPD))wake_all_kswapd(order, zonelist, high_zoneidx,zone_idx(preferred_zone));/*为了更积极地尝试分配，将水位线降低以便更有可能分配成功。*/alloc_flags = gfp_to_alloc_flags(gfp_mask);/* * Find the true preferred zone if the allocation is unconstrained by * cpusets. */if (!(alloc_flags & ALLOC_CPUSET) && !nodemask)first_zones_zonelist(zonelist, high_zoneidx, NULL,&preferred_zone);rebalance:/*降低水位线之后重新尝试分配。*//* This is the last chance, in general, before the goto nopage. */page = get_page_from_freelist(gfp_mask, nodemask, order, zonelist,high_zoneidx, alloc_flags & ~ALLOC_NO_WATERMARKS,preferred_zone, migratetype);if (page)goto got_pg;/*如果不考虑水位线，那么继续尝试分配。如果定义了__GFP_NOFAIL，那么此函数会不断尝试分配，直到成功。*//* Allocate without watermarks if the context allows */if (alloc_flags & ALLOC_NO_WATERMARKS) {page = __alloc_pages_high_priority(gfp_mask, order,zonelist, high_zoneidx, nodemask,preferred_zone, migratetype);if (page)goto got_pg;}/*没定义等待，如在中断上下文中需要原子份额配，所以直接返回失败。*//* Atomic allocations - we can't balance anything */if (!wait)goto nopage;/*分配器自身需要更多内存，避免递归调用。*//* Avoid recursion of direct reclaim */if (current->flags & PF_MEMALLOC)goto nopage;/*oom killer选中的线程才会设置TIF_MEMDIE标志，当然如果不允许失败的话那就循环等待其他线程释放内存。*//* Avoid allocations with no watermarks from looping endlessly */if (test_thread_flag(TIF_MEMDIE) && !(gfp_mask & __GFP_NOFAIL))goto nopage;/*尝试压缩内存再尝试分配。*/page = __alloc_pages_direct_compact(gfp_mask, order,zonelist, high_zoneidx,nodemask,alloc_flags, preferred_zone,migratetype, sync_migration,&deferred_compaction,&did_some_progress);if (page)goto got_pg;~~snip/*自己直接去回收内存，然后尝试分配。*//* Try direct reclaim and then allocating */page = __alloc_pages_direct_reclaim(gfp_mask, order,zonelist, high_zoneidx,nodemask,alloc_flags, preferred_zone,migratetype, &did_some_progress);if (page)goto got_pg;/*如果还是失败的话那就使用oom killer杀掉一些线程，再尝试分配。*/if (!did_some_progress) {if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {if (oom_killer_disabled)goto nopage;/* Coredumps can quickly deplete all memory reserves */if ((current->flags & PF_DUMPCORE) &&    !(gfp_mask & __GFP_NOFAIL))goto nopage;page = __alloc_pages_may_oom(gfp_mask, order,zonelist, high_zoneidx,nodemask, preferred_zone,migratetype);if (page)goto got_pg;if (!(gfp_mask & __GFP_NOFAIL)) {/* * The oom killer is not called for high-order * allocations that may fail, so if no progress * is being made, there are no other options and * retrying is unlikely to help. */if (order > PAGE_ALLOC_COSTLY_ORDER)goto nopage;/* * The oom killer is not called for lowmem * allocations to prevent needlessly killing * innocent tasks. */if (high_zoneidx < ZONE_NORMAL)goto nopage;}goto restart;}}/*是否需要等待一会再尝试重新分配?*//* Check if we should retry the allocation */pages_reclaimed += did_some_progress;if (should_alloc_retry(gfp_mask, order, did_some_progress,pages_reclaimed)) {/* Wait for some write requests to complete then retry */wait_iff_congested(preferred_zone, BLK_RW_ASYNC, HZ/50);goto rebalance;} else {/*在做过内存回收之后再使用内存压缩分配试试看。*/page = __alloc_pages_direct_compact(gfp_mask, order,zonelist, high_zoneidx,nodemask,alloc_flags, preferred_zone,migratetype, sync_migration,&deferred_compaction,&did_some_progress);if (page)goto got_pg;}/*到这里表示真分配失败了，打印警告信息。*/nopage:warn_alloc_failed(gfp_mask, order, NULL);return page;got_pg:if (kmemcheck_enabled)kmemcheck_pagealloc_alloc(page, order, gfp_mask);return page;}
内存分配一波三折，小结一下：
1.      先尝试快速分配，其中会从不同的zone以及迁移类型上去尝试，失败的话就进入慢速分配，里面会再划分单页面从pcp上分配以及多页面从伙伴系统中分配。
2.      尝试慢速分配，一般流程就是唤醒内存页面回收线程，然后尝试低水位分配 -> 忽略水位分配 -> 压缩内存分配 -> 直接回收内存分配 -> oom killer杀死线程分配 -> 压缩内存分配。
内存释放：
         关于内存释放，使用的最终公共接口为__free_pages, 流程部分还是比较清晰的，
这里不对代码作具体分析了。分单页和多页释放。
单页：释放到pcp缓冲中，如果pcp中的空闲页面数过多，就会移动一部分到伙伴系统中。
多页：释放多页到伙伴系统，当当前的释放页面数和相邻的空闲页面数相同时，那就将两者合并，然后放到更高一阶的order链表上面，依次循环执行次操作直到不能合并为止。
  
2013/04/07