【Linux内存源码分析】伙伴管理算法(1)

前面分析了memblock算法、内核页表的建立、内存管理框架的构建,这些都是x86处理的setup_arch()函数里面初始化的,因地制宜,具有明显处理器的特征。而start_kernel()接下来的初始化则是linux通用的内存管理算法框架了。

build_all_zonelists()用来初始化内存分配器使用的存储节点中的管理区链表,是为内存管理算法(伙伴管理算法)做准备工作的。具体实现:

【file:/mm/page_alloc.c】
/*
 * Called with zonelists_mutex held always
 * unless system_state == SYSTEM_BOOTING.
 */
void __ref build_all_zonelists(pg_data_t *pgdat, struct zone *zone)
{
	set_zonelist_order();

	if (system_state == SYSTEM_BOOTING) {
		__build_all_zonelists(NULL);
		mminit_verify_zonelist();
		cpuset_init_current_mems_allowed();
	} else {
#ifdef CONFIG_MEMORY_HOTPLUG
		if (zone)
			setup_zone_pageset(zone);
#endif
		/* we have to stop all cpus to guarantee there is no user
		   of zonelist */
		stop_machine(__build_all_zonelists, pgdat, NULL);
		/* cpuset refresh routine should be here */
	}
	vm_total_pages = nr_free_pagecache_pages();
	/*
	 * Disable grouping by mobility if the number of pages in the
	 * system is too low to allow the mechanism to work. It would be
	 * more accurate, but expensive to check per-zone. This check is
	 * made on memory-hotadd so a system can start with mobility
	 * disabled and enable it later
	 */
	if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))
		page_group_by_mobility_disabled = 1;
	else
		page_group_by_mobility_disabled = 0;

	printk("Built %i zonelists in %s order, mobility grouping %s.  "
		"Total pages: %ld\n",
			nr_online_nodes,
			zonelist_order_name[current_zonelist_order],
			page_group_by_mobility_disabled ? "off" : "on",
			vm_total_pages);
#ifdef CONFIG_NUMA
	printk("Policy zone: %s\n", zone_names[policy_zone]);
#endif
}

    首先看到set_zonelist_order()

【file:/mm/page_alloc.c】
static void set_zonelist_order(void)
{
	current_zonelist_order = ZONELIST_ORDER_ZONE;
}

此处用于设置zonelist的顺序,ZONELIST_ORDER_ZONE用于表示顺序(-zonetype, [node]
distance)
,另外还有ZONELIST_ORDER_NODE表示顺序([node] distance, -zonetype)。但其仅限于对NUMA环境存在区别,非NUMA环境则毫无差异。

如果系统状态system_stateSYSTEM_BOOTING,系统状态只有在start_kernel执行到最后一个函数rest_init后,才会进入SYSTEM_RUNNING,于是初始化时将会接着是__build_all_zonelists()函数:

【file:/mm/page_alloc.c】
/* return values int ....just for stop_machine() */
static int __build_all_zonelists(void *data)
{
	int nid;
	int cpu;
	pg_data_t *self = data;

#ifdef CONFIG_NUMA
	memset(node_load, 0, sizeof(node_load));
#endif

	if (self && !node_online(self->node_id)) {
		build_zonelists(self);
		build_zonelist_cache(self);
	}

	for_each_online_node(nid) {
		pg_data_t *pgdat = NODE_DATA(nid);

		build_zonelists(pgdat);
		build_zonelist_cache(pgdat);
	}

	/*
	 * Initialize the boot_pagesets that are going to be used
	 * for bootstrapping processors. The real pagesets for
	 * each zone will be allocated later when the per cpu
	 * allocator is available.
	 *
	 * boot_pagesets are used also for bootstrapping offline
	 * cpus if the system is already booted because the pagesets
	 * are needed to initialize allocators on a specific cpu too.
	 * F.e. the percpu allocator needs the page allocator which
	 * needs the percpu allocator in order to allocate its pagesets
	 * (a chicken-egg dilemma).
	 */
	for_each_possible_cpu(cpu) {
		setup_pageset(&per_cpu(boot_pageset, cpu), 0);

#ifdef CONFIG_HAVE_MEMORYLESS_NODES
		/*
		 * We now know the "local memory node" for each node--
		 * i.e., the node of the first zone in the generic zonelist.
		 * Set up numa_mem percpu variable for on-line cpus.  During
		 * boot, only the boot cpu should be on-line;  we'll init the
		 * secondary cpus' numa_mem as they come on-line.  During
		 * node/memory hotplug, we'll fixup all on-line cpus.
		 */
		if (cpu_online(cpu))
			set_cpu_numa_mem(cpu, local_memory_node(cpu_to_node(cpu)));
#endif
	}

	return 0;
}

    首先分析该函数里面调用的build_zonelists()build_zonelist_cache()函数,其中build_zonelists()

【file:/mm/page_alloc.c】
static void build_zonelists(pg_data_t *pgdat)
{
	int node, local_node;
	enum zone_type j;
	struct zonelist *zonelist;

	local_node = pgdat->node_id;

	zonelist = &pgdat->node_zonelists[0];
	j = build_zonelists_node(pgdat, zonelist, 0);

	/*
	 * Now we build the zonelist so that it contains the zones
	 * of all the other nodes.
	 * We don't want to pressure a particular node, so when
	 * building the zones for node N, we make sure that the
	 * zones coming right after the local ones are those from
	 * node N+1 (modulo N)
	 */
	for (node = local_node + 1; node < MAX_NUMNODES; node++) {
		if (!node_online(node))
			continue;
		j = build_zonelists_node(NODE_DATA(node), zonelist, j);
	}
	for (node = 0; node < local_node; node++) {
		if (!node_online(node))
			continue;
		j = build_zonelists_node(NODE_DATA(node), zonelist, j);
	}

	zonelist->_zonerefs[j].zone = NULL;
	zonelist->_zonerefs[j].zone_idx = 0;
}

    其中build_zonelists_node()函数实现:

【file:/mm/page_alloc.c】
/*
 * Builds allocation fallback zone lists.
 *
 * Add all populated zones of a node to the zonelist.
 */
static int build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
				int nr_zones)
{
	struct zone *zone;
	enum zone_type zone_type = MAX_NR_ZONES;

	do {
		zone_type--;
		zone = pgdat->node_zones + zone_type;
		if (populated_zone(zone)) {
			zoneref_set_zone(zone,
				&zonelist->_zonerefs[nr_zones++]);
			check_highest_zone(zone_type);
		}
	} while (zone_type);

	return nr_zones;
}

populated_zone()用于判断管理区zonepresent_pages成员是否为0,如果不为0的话,表示该管理区存在页面,那么则通过zoneref_set_zone()将其设置到zonelist_zonerefs里面,而check_highest_zone()在没有开启NUMA的情况下是个空函数。由此可以看出build_zonelists_node()实则上是按照ZONE_HIGHMEM—>ZONE_NORMAL—>ZONE_DMA的顺序去迭代排布到_zonerefs里面的,表示一个申请内存的代价由低廉到昂贵的顺序,这是一个分配内存时的备用次序。

回到build_zonelists()函数中,而它代码显示将本地的内存管理区进行分配备用次序排序,接着再是分配内存代价低于本地的,最后才是分配内存代价高于本地的。

分析完build_zonelists(),再回到__build_all_zonelists()看一下build_zonelist_cache()

【file:/mm/page_alloc.c】
/* non-NUMA variant of zonelist performance cache - just NULL zlcache_ptr */
static void build_zonelist_cache(pg_data_t *pgdat)
{
	pgdat->node_zonelists[0].zlcache_ptr = NULL;
}

该函数与CONFIG_NUMA相关,用来设置zlcache相关的成员。由于没有开启该配置,故直接设置为NULL

基于build_all_zonelists()调用__build_all_zonelists()入参为NULL,由此可知__build_all_zonelists()运行的代码是:

    for_each_online_node(nid) {

       pg_data_t *pgdat = NODE_DATA(nid);

       build_zonelists(pgdat);

       build_zonelist_cache(pgdat);

    }

主要是设置各个内存管理节点node里面各自的内存管理分区zone的内存分配次序。

__build_all_zonelists()接着的是:

    for_each_possible_cpu(cpu) {

       setup_pageset(&per_cpu(boot_pageset, cpu), 0);

#ifdef
CONFIG_HAVE_MEMORYLESS_NODES

       if (cpu_online(cpu))

           set_cpu_numa_mem(cpu,
local_memory_node(cpu_to_node(cpu)));

#endif

    }

其中CONFIG_HAVE_MEMORYLESS_NODES未配置,主要分析一下setup_pageset()

【file:/mm/page_alloc.c】
static void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
{
	pageset_init(p);
	pageset_set_batch(p, batch);
}

setup_pageset()里面调用的两个函数较为简单,就直接过一下。先是:

【file:/mm/page_alloc.c】
static void pageset_init(struct per_cpu_pageset *p)
{
	struct per_cpu_pages *pcp;
	int migratetype;

	memset(p, 0, sizeof(*p));

	pcp = &p->pcp;
	pcp->count = 0;
	for (migratetype = 0; migratetype < MIGRATE_PCPTYPES; migratetype++)
		INIT_LIST_HEAD(&pcp->lists[migratetype]);
}

        pageset_init()主要是将struct per_cpu_pages结构体进行初始化,而pageset_set_batch()则是对其进行设置。pageset_set_batch()实现:

【file:/mm/page_alloc.c】
/*
 * pcp->high and pcp->batch values are related and dependent on one another:
 * ->batch must never be higher then ->high.
 * The following function updates them in a safe manner without read side
 * locking.
 *
 * Any new users of pcp->batch and pcp->high should ensure they can cope with
 * those fields changing asynchronously (acording the the above rule).
 *
 * mutex_is_locked(&pcp_batch_high_lock) required when calling this function
 * outside of boot time (or some other assurance that no concurrent updaters
 * exist).
 */
static void pageset_update(struct per_cpu_pages *pcp, unsigned long high,
		unsigned long batch)
{
       /* start with a fail safe value for batch */
	pcp->batch = 1;
	smp_wmb();

       /* Update high, then batch, in order */
	pcp->high = high;
	smp_wmb();

	pcp->batch = batch;
}

/* a companion to pageset_set_high() */
static void pageset_set_batch(struct per_cpu_pageset *p, unsigned long batch)
{
	pageset_update(&p->pcp, 6 * batch, max(1UL, 1 * batch));
}

setup_pageset()函数入参p是一个struct per_cpu_pageset结构体的指针,per_cpu_pageset结构是内核的各个zone用于每CPU的页面高速缓存管理结构。该高速缓存包含一些预先分配的页面,以用于满足本地CPU发出的单一内存请求。而struct per_cpu_pages定义的pcp是该管理结构的成员,用于具体页面管理。原本是每个管理结构有两个pcp数组成员,里面的两条队列分别用于冷页面和热页面管理,而当前分析的3.14.12版本已经将两者合并起来,统一管理冷热页,热页面在队列前面,而冷页面则在队列后面。暂且先记着这么多,后续在Buddy算法的时候再详细分析了。

至此,可以知道__build_all_zonelists()是内存管理框架向后续的内存页面管理算法做准备,排布了内存管理区zone的分配次序,同时初始化了冷热页管理。

最后回到build_all_zonelists()函数。由于没有开启内存初始化调试功能CONFIG_DEBUG_MEMORY_INITmminit_verify_zonelist()是一个空函数。

基于CONFIG_CPUSETS配置项开启的情况下,而cpuset_init_current_mems_allowed()实现如下:

【file:/kernel/cpuset.c】
void cpuset_init_current_mems_allowed(void)
{
	nodes_setall(current->mems_allowed);
}

这里面的current 是一个cpuset的数据结构,用来管理cgroup中的任务能够使用的cpu和内存节点。而成员mems_allowed,该成员是nodemask_t类型的结构体:

【file:/include/linux/nodemask.h】
typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;

该结构其实就是定义了一个位域,每个位对应一个内存节点,如果置1表示该节点内存可用。而nodes_setall则是将这个位域中每个位都置1

末了看一下build_all_zonelists()里面nr_free_pagecache_pages()的实现:

【file:/mm/page_alloc.c】
/**
 * nr_free_pagecache_pages - count number of pages beyond high watermark
 *
 * nr_free_pagecache_pages() counts the number of pages which are beyond the
 * high watermark within all zones.
 */
unsigned long nr_free_pagecache_pages(void)
{
	return nr_free_zone_pages(gfp_zone(GFP_HIGHUSER_MOVABLE));
}

        而里面调用的nr_free_zone_pages()实现为:

【file:/mm/page_alloc.c】
/**
 * nr_free_zone_pages - count number of pages beyond high watermark
 * @offset: The zone index of the highest zone
 *
 * nr_free_zone_pages() counts the number of counts pages which are beyond the
 * high watermark within all zones at or below a given zone index.  For each
 * zone, the number of pages is calculated as:
 *     managed_pages - high_pages
 */
static unsigned long nr_free_zone_pages(int offset)
{
	struct zoneref *z;
	struct zone *zone;

	/* Just pick one node, since fallback list is circular */
	unsigned long sum = 0;

	struct zonelist *zonelist = node_zonelist(numa_node_id(), GFP_KERNEL);

	for_each_zone_zonelist(zone, z, zonelist, offset) {
		unsigned long size = zone->managed_pages;
		unsigned long high = high_wmark_pages(zone);
		if (size > high)
			sum += size - high;
	}

	return sum;
}

可以看到nr_free_zone_pages()遍历所有内存管理区并将各管理区的内存空间求和,其实质是用于统计所有的管理区可以用于分配的内存页面数。

接着在build_all_zonelists()后面则是判断当前系统中的内存页框数目,以决定是否启用流动分组机制(Mobility Grouping),该机制可以在分配大内存块时减少内存碎片。通常只有内存足够大时才会启用该功能,否则将会提升消耗降低性能。其中pageblock_nr_pages表示伙伴系统中的最高阶页块所能包含的页面数。

至此,内存管理框架算法基本准备完毕。

而接着的page_alloc_init()实现:

【file:/mm/page_alloc.c】
void __init page_alloc_init(void)
{
	hotcpu_notifier(page_alloc_cpu_notify, 0);
}

其中hotcpu_notifier是一个宏定义:

【file:/include/linux/cpu.h】
#define hotcpu_notifier(fn, pri)	cpu_notifier(fn, pri)

它仅当CONFIG_HOTPLUG_CPU配置开启时,有以上的定义,用于对每个CPU的通告作用。展开如下:

【file:/include/linux/cpu.h】
#define cpu_notifier(fn, pri) {					\
	static struct notifier_block fn##_nb =			\
		{ .notifier_call = fn, .priority = pri };	\
	register_cpu_notifier(&fn##_nb);			\
}

如果没有定义CONFIG_HOTPLUG_CPU时,则为:

【file:/include/linux/cpu.h】
#define hotcpu_notifier(fn, pri)	do { (void)(fn); } while (0)

        无任何功能作用。

发表评论

电子邮件地址不会被公开。 必填项已用*标注