精华内容
下载资源
问答
  • linux内存伙伴算法(四:释放页)

    千次阅读 2012-09-07 10:43:31
    if (reserved)//如果在需要释放的一段内存中有需要保留的内存页,那么该段内存就不能释放 return; if (!PageHighMem(page))//判断页是否在高端内存域中 debug_check_no_locks_freed(page_address(page),PAGE_...

    __free_pages源代码详细分析如下:

    fastcall void __free_pages(struct page *page, unsigned int order)
    {
    	if (put_page_testzero(page)) {//一般来说,只有当页面的引用计数变为0时,才会释放该页,此处进行页面引用计数的判断
    		if (order == 0)//如果是释放单个页面,则释放到管理区的每CPU页面缓存中,以加快单页分配速度
    			free_hot_page(page);
    		else
    			__free_pages_ok(page, order);//否则直接释放到伙伴系统中 
    	}
    }
    void fastcall free_hot_page(struct page *page)
    {
    	free_hot_cold_page(page, 0);
    }
    free_hot_cold_page源代码详细分析如下:
    
    static void fastcall free_hot_cold_page(struct page *page, int cold)
    {
    	struct zone *zone = page_zone(page);//找到页面所属的管理区
    	struct per_cpu_pages *pcp;//为等下访问冷热区做准备,pcp是一个中间变量
    	unsigned long flags;
    
    	if (PageAnon(page))//说明page->mapping的第0位是1,说明该页是匿名页
    		page->mapping = NULL;//则使page->mapping指向NULL
    	if (free_pages_check(page))//这个函数就是检测page的flag和mapping,_count,_mapcount这几个成员,如果有误,就会进行相应的处理
    		return;
    
    	if (!PageHighMem(page))//如果该内存页不在高端内存域
    		debug_check_no_locks_freed(page_address(page), PAGE_SIZE);//则调试相关代码
    	arch_free_page(page, 0);//只有配置了HAVE_ARCH_FREE_PAGE才会起作用
    	kernel_map_pages(page, 1, 0);
    
    	pcp = &zone_pcp(zone, get_cpu())->pcp[cold];//获得本页区的当前cpu,然后找到对应的热区的高速缓存内存,用pcp指针指向它
    	local_irq_save(flags);//禁止irq中断
    	__count_vm_event(PGFREE);//统计本CPU上的页面释放次数
    	list_add(&page->lru, &pcp->list);//把page的lru挂在pcp->list上,挂在pcp->list前面
    	set_page_private(page, get_pageblock_migratetype(page));//获取页面的迁移类型,并将其保存在page->private中
    	pcp->count++;//更新当前CPU页面缓存计数
    	if (pcp->count >= pcp->high) {//页面缓存中保留的页面太多,超过上限了
    		free_pages_bulk(zone, pcp->batch, &pcp->list, 0);//将页面缓存中的页面释放一部分到伙伴系统中
    		pcp->count -= pcp->batch;//更新当前CPU中页面缓存计数
    	}
    	local_irq_restore(flags);//恢复中断
    	put_cpu();//preempt_enable()是抢占使能
    }
    
    free_pages_bulk源代码详细分析如下:
    static void free_pages_bulk(struct zone *zone, int count,
    					struct list_head *list, int order)
    {
    	spin_lock(&zone->lock);//上锁
    	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);//在释放页之前,先将内存区中页不可回收的标志清除
    	zone->pages_scanned = 0;//在上一次成功换出页之后,已扫描页计数器
    	while (count--) {//循环,直到把count个页面全部释放
    		struct page *page;
    
    		VM_BUG_ON(list_empty(list));
    		page = list_entry(list->prev, struct page, lru);//通过pcp->list找到第一个lru,再通过lru成员找到对应的struct page
    		/* have to delete it as __free_one_page list manipulates */
    		list_del(&page->lru);//lru取出后,pcp->list链表就不再指向它了,就要从链表里面移除
    		__free_one_page(page, zone, order);//这是释放函数的主体,下面会详细讨论
    	}
    	spin_unlock(&zone->lock);//解锁
    }
    
    _free_pages_ok源代码详细分析如下:
    static void __free_pages_ok(struct page *page, unsigned int order)
    {
    	unsigned long flags;
    	int i;
    	int reserved = 0;
    
    	for (i = 0 ; i < (1 << order) ; ++i)
    		reserved += free_pages_check(page + i);//在释放页之前,还得先用free_pages_check函数检查页是否有错误,如果有错误就要进行相应的处理,如果没有错误,还需要记录所有页面中需要保留的页面数
    	if (reserved)//如果在需要释放的一段内存中有需要保留的内存页,那么该段内存就不能释放
    		return;
    
    	if (!PageHighMem(page))//判断页是否在高端内存域中
    		debug_check_no_locks_freed(page_address(page),PAGE_SIZE<<order);//调试用的相关代码,还不理解,还望指点!
    	arch_free_page(page, order);//只有配置了HAVE_ARCH_FREE_PAGE才会起作用,也不理解,还望指点
    	kernel_map_pages(page, 1 << order, 0);
    
    	local_irq_save(flags);//禁止中断
    	__count_vm_events(PGFREE, 1 << order);//统计本CPU上释放的页数
    	free_one_page(page_zone(page), page, order);//释放函数的主体__free_one_page的封装
    	local_irq_restore(flags);//恢复中断
    }
    
    static void free_one_page(struct zone *zone, struct page *page, int order)
    {
    	spin_lock(&zone->lock);//获得管理区得自旋锁
    	zone_clear_flag(zone, ZONE_ALL_UNRECLAIMABLE);//在释放之前,先将内存区中页的不可回收标志清除
    	zone->pages_scanned = 0;//初始化在上一次成功换出页之后,已扫描页的数目。目前正在释放内存,将此清0,待回收过程随后回收时重新计数
    	__free_one_page(page, zone, order);//释放函数的主体
    	spin_unlock(&zone->lock);//解锁,有关锁的机制,自己还没有看到,后面的Blog会详细分析
    }
    
    __free_one_page源代码详细分析如下:
    static inline void __free_one_page(struct page *page,
    		struct zone *zone, unsigned int order)
    {
    	unsigned long page_idx;
    	int order_size = 1 << order;
    	int migratetype = get_pageblock_migratetype(page);
    
    	if (unlikely(PageCompound(page)))//要释放的页是巨页的一部分
    		destroy_compound_page(page, order);//解决巨页标志,如果巨页标志有问题,则退出
    
    	page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);//获取该页得页帧号,并保证该值在一定的范围之内
    
    	VM_BUG_ON(page_idx & (order_size - 1));//如果被释放的页不是所释放阶的第一个页,则说明参数有误
    	VM_BUG_ON(bad_range(zone, page));//检查页面是否处于zone之中
    
    	__mod_zone_page_state(zone, NR_FREE_PAGES, order_size);
    	while (order < MAX_ORDER-1) {//释放页以后,当前页面可能与前后的空闲页组成更大的空闲页面,直到放到最大阶的伙伴系统中
    		unsigned long combined_idx;
    		struct page *buddy;
    
    		buddy = __page_find_buddy(page, page_idx, order);//找到与当前页属于同一个阶的伙伴系统页面的索引
    		if (!page_is_buddy(page, buddy, order))//判断预期的伙伴页面是否与当前页处于同一个管理区,并且是否处于空闲状态。如果不是,则不能与该页合并为大的伙伴,退出
    			break;		/* Move the buddy up one level. */
    
    		list_del(&buddy->lru);//如果能够合并,则将伙伴页从伙伴系统中摘除
    		zone->free_area[order].nr_free--;//同时减少当前阶中的空闲页计数
    		rmv_page_order(buddy);//清除伙伴页的伙伴标志,因为该页会被合并
    		combined_idx = __find_combined_index(page_idx, order);//计算合并内存块的索引
    		page = page + (combined_idx - page_idx);//得到新的页面起始地址
    		page_idx = combined_idx;//为下一轮循环做准备
    		order++;//为下一轮循环做准备
    	}
    	set_page_order(page, order);//设置伙伴页中第一个空闲页的阶
    	list_add(&page->lru,
    		&zone->free_area[order].free_list[migratetype]);//将当前页面合并到空闲链表的最后,尽量避免将它分配出去
    	zone->free_area[order].nr_free++;
    }
    
    
    我只是一个内核的初学者,如果有哪些地方说的不对或是不准确,请指正;如果你有什么问题希望能提出来,一起分析讨论一下,以求共同进步。谢谢!
    
    
    
    
    
    
    展开全文
  • linux内存伙伴算法(三:分配页)

    千次阅读 2012-09-04 11:20:53
    伙伴系统中用于分配页的函数如下: alloc_pages(mask,order)分配2^order页并返回一个struct page的实例,表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式,只分配一页。 get_zeroed_...

    伙伴系统中用于分配页的函数如下:

    alloc_pages(mask,order)分配2^order页并返回一个struct page的实例,表示分配的内存块的起始页。alloc_page(mask)是前者在order=0情况下的简化形式,只分配一页。

    get_zeroed_page(mask)分配一页并返回一个page实例,页对应的内存填充0(所有其他函数分配之后的内容是未定义的)。

    __get_free_pages(mask,order)和__get_free_page(mask)的工作方式与上述函数相同,但返回分配内存块的虚拟地址,而不是page实例。

    get_dma_pages(gfp_mask,order)用来获得适用于DMA的页。

    在空闲内存无法满足请求以至于分配失败的情况下,所有上述函数都返回空指针(alloc_pages和alloc_page)或者0(get_zeroed_page、__get_free_pages和__get_free_page)。因此内核在各次分配之后必须检查返回的结果。这种惯例与设计得很好的用户层应用程序没有什么不同,但在内核中忽略检查将会导致严重得多的故障。

    前述所有函数中使用的mask参数的语义是什么?linux将内核划分为内存域,内核提供了所谓的内存域修饰符,来指定从哪个内存域分配所需的页。

    #define __GFP_DMA	((__force gfp_t)0x01u)
    #define __GFP_HIGHMEM	((__force gfp_t)0x02u)
    #define __GFP_DMA32	((__force gfp_t)0x04u)
    
    除了内存域修饰符之外,掩码中还可以设置一些标志,这些额外的标志并不限制从哪个物理内存段分配内存,但确实可以改变分配器的行为。

    #define __GFP_WAIT	((__force gfp_t)0x10u)	//表示分配内存的请求可以中断。也就是说,调度器在该请求期间可随意选择另一个过程执行,或者该请求可以被另一个更重要的事件中断。
    #define __GFP_HIGH	((__force gfp_t)0x20u)	//如果请求非常重要,则设置__GFP_HIGH,即内核急切的需要内存时。在分配内存失败可能给内核带来严重得后果时,一般会设置该标志
    #define __GFP_IO	((__force gfp_t)0x40u)	//在查找空闲内存期间内核可以进行I/O操作。这意味着如果内核在内存分配期间换出页,那么仅当设置该标志时,才能将选择的页写入磁盘。
    #define __GFP_FS	((__force gfp_t)0x80u)	//允许内核执行VFS操作
    #define __GFP_COLD	((__force gfp_t)0x100u)	//如果需要分配不在CPU高速缓存中的“冷”页时,则设置__GFP_COLD。
    #define __GFP_NOWARN	((__force gfp_t)0x200u)	//在分配失败时禁止内核故障警告。
    #define __GFP_REPEAT	((__force gfp_t)0x400u)	//在分配失败后自动重试,但在尝试若干次之后会停止。
    #define __GFP_NOFAIL	((__force gfp_t)0x800u)	//在分配失败后一直重试,直至成功。
    #define __GFP_NORETRY	((__force gfp_t)0x1000u)//不重试,可能失败
    #define __GFP_COMP	((__force gfp_t)0x4000u)//增加复合页元数据
    #define __GFP_ZERO	((__force gfp_t)0x8000u)//在分配成功时,将返回填充字节0的页。
    #define __GFP_NOMEMALLOC ((__force gfp_t)0x10000u) //不适用紧急分配链表
    #define __GFP_HARDWALL   ((__force gfp_t)0x20000u) //只在NUMA系统上有意义。它限制只在分配到当前进程的各个CPU所关联的结点分配内存。如果进程允许在所有的CPU上运行(默认情况下),该标志是没有意义的。只有进程可以运行的CPU受限时,该标志才有意义。
    #define __GFP_THISNODE	((__force gfp_t)0x40000u)//页只在NUMA系统上有意义,如果设置该比特位,则内存分配失败的情况下不允许使用其他结点作为备用,需要保证在当前结点或者明确指定的结点上成功分配内存。
    #define __GFP_RECLAIMABLE ((__force gfp_t)0x80000u) //将分配的内存标记为可回收
    #define __GFP_MOVABLE	((__force gfp_t)0x100000u)  //将分配的内存标记为可移动
    
    #define __GFP_BITS_SHIFT 21	/* Room for 21 __GFP_FOO bits */
    #define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))
    
    /* This equals 0, but use constants in case they ever change */
    #define GFP_NOWAIT	(GFP_ATOMIC & ~__GFP_HIGH)
    由于这些标志总是组合使用,内核做了一些分组,包含了用于各种标准情形的适当地标志。

    #define GFP_ATOMIC	(__GFP_HIGH)//用于原子分配,在任何情况下都不能中断,可能使用紧急分配链表中的内存
    #define GFP_NOIO	(__GFP_WAIT)//明确禁止IO操作,但可以被中断
    #define GFP_NOFS	(__GFP_WAIT | __GFP_IO)//明确禁止访问VFS层操作,但可以被中断
    #define GFP_KERNEL	(__GFP_WAIT | __GFP_IO | __GFP_FS)//内核分配的默认配置
    #define GFP_TEMPORARY	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    			 __GFP_RECLAIMABLE)
    #define GFP_USER	(__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL)//用户分配的默认配置
    #define GFP_HIGHUSER	(__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HARDWALL | \
    			 __GFP_HIGHMEM)//是GFP_USER的一个扩展,页用于用户空间,它允许分配无法直接映射的高端内存,使用高端内存页是没有坏处的,因为用户过程的地址空间总是通过非线性页表组织的
    #define GFP_HIGHUSER_MOVABLE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_HIGHMEM | \
    				 __GFP_MOVABLE)//类似于GFP_HIGHUSER,但分配是在虚拟内存域ZONE_MOVABLE中进行
    #define GFP_NOFS_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_MOVABLE)
    #define GFP_USER_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_MOVABLE)
    #define GFP_HIGHUSER_PAGECACHE	(__GFP_WAIT | __GFP_IO | __GFP_FS | \
    				 __GFP_HARDWALL | __GFP_HIGHMEM | \
    				 __GFP_MOVABLE)
    
    #ifdef CONFIG_NUMA
    #define GFP_THISNODE	(__GFP_THISNODE | __GFP_NOWARN | __GFP_NORETRY)
    #else
    #define GFP_THISNODE	((__force gfp_t)0)
    #endif
    
    /* This mask makes up all the page movable related flags */
    #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)
    
    /* Control page allocator reclaim behavior */
    #define GFP_RECLAIM_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS|\
    			__GFP_NOWARN|__GFP_REPEAT|__GFP_NOFAIL|\
    			__GFP_NORETRY|__GFP_NOMEMALLOC)
    
    /* Control allocation constraints */
    #define GFP_CONSTRAINT_MASK (__GFP_HARDWALL|__GFP_THISNODE)
    
    /* Do not use these with a slab allocator */
    #define GFP_SLAB_BUG_MASK (__GFP_DMA32|__GFP_HIGHMEM|~__GFP_BITS_MASK)
    
    /* Flag - indicates that the buffer will be suitable for DMA.  Ignored on some
       platforms, used as appropriate on others */
    
    #define GFP_DMA		__GFP_DMA
    
    /* 4GB DMA on some platforms */
    #define GFP_DMA32	__GFP_DMA32
    #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
    #define __get_free_page(gfp_mask) \
    		__get_free_pages((gfp_mask),0)
    #define __get_dma_pages(gfp_mask, order) \
    		__get_free_pages((gfp_mask) | GFP_DMA,(order))
    fastcall unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
    {
    	struct page * page;
    	page = alloc_pages(gfp_mask, order);
    	if (!page)
    		return 0;
    	return (unsigned long) page_address(page);
    }
    #define alloc_pages(gfp_mask, order) \
    		alloc_pages_node(numa_node_id(), gfp_mask, order)
    根据上面的代码,可以得出各个分配函数之间的关系如下图所示:


    主要的函数是alloc_pages_node。alloc_pages_node源代码的详细分析如下:

    static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
    						unsigned int order)
    {
    	if (unlikely(order >= MAX_ORDER))//执行一个检查,避免分配过大的内存块
    		return NULL;
    
    	/* Unknown node is current node */
    	if (nid < 0)//如果指定负的结点ID(不存在),内核自动地使用当前执行CPU对应的结点ID。
    		nid = numa_node_id();
    
    	return __alloc_pages(gfp_mask, order,
    		NODE_DATA(nid)->node_zonelists + gfp_zone(gfp_mask));//接下来的工作委托给__alloc_pages,只需传递一组适当地参数,请注意,gfp_zone用于选择分配内存的内存域。
    }

    static inline enum zone_type gfp_zone(gfp_t flags)//本函数比较好理解,就是根据指定的标志确定内存域
    {
    	int base = 0;
    
    #ifdef CONFIG_NUMA
    	if (flags & __GFP_THISNODE)
    		base = MAX_NR_ZONES;
    #endif
    
    #ifdef CONFIG_ZONE_DMA
    	if (flags & __GFP_DMA)
    		return base + ZONE_DMA;
    #endif
    #ifdef CONFIG_ZONE_DMA32
    	if (flags & __GFP_DMA32)
    		return base + ZONE_DMA32;
    #endif
    	if ((flags & (__GFP_HIGHMEM | __GFP_MOVABLE)) ==
    			(__GFP_HIGHMEM | __GFP_MOVABLE))
    		return base + ZONE_MOVABLE;
    #ifdef CONFIG_HIGHMEM
    	if (flags & __GFP_HIGHMEM)
    		return base + ZONE_HIGHMEM;
    #endif
    	return base + ZONE_NORMAL;
    }

    __alloc_pages源代码详细分析如下:

    __alloc_pages(gfp_t gfp_mask, unsigned int order,
    		struct zonelist *zonelist)//gfp_mask是一些标志位,用来制定如何寻找空闲页框,order用来表示所需物理块的大小,从空闲链表中获取2^order页内存,在管理区链表zonelist中依次查找每个区,从中找到满足要求的区
    {
    	const gfp_t wait = gfp_mask & __GFP_WAIT;//gfp_mask是申请内存时用到的控制字,这一句就是为了检测我们的控制字里面是否有__GPF_WAIT这个属性
    	struct zone **z;//管理区结构体
    	struct page *page;
    	struct reclaim_state reclaim_state;
    	struct task_struct *p = current;
    	int do_retry;
    	int alloc_flags;
    	int did_some_progress;
    
    	might_sleep_if(wait);//如果在gfp_mask中设置了__GFP_WAIT位,表明内核可以阻塞当前进程,来等待空闲页面。在分配开始之前即阻塞,目的是为了等待其它进程释放更多的页面
    
    	if (should_fail_alloc_page(gfp_mask, order))//通过简单算法在真正分配前检查分配是否会失败,避免进入真正的分配程序后浪费系统时间
    		return NULL;
    
    restart:
    	z = zonelist->zones;//zonelist是struct node中的一个成员,它表示系统内所有normal内存页区的连接链表,首先让z指向第一个管理区
    
    	if (unlikely(*z == NULL)) {//如果发现头指针为空,即没有指向struct zone的有效指针,我们就直接返回错误
    		/*
    		 * Happens if we have an empty zonelist as a result of
    		 * GFP_THISNODE being used on a memoryless node
    		 */
    		return NULL;
    	}
    
    	page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
    				zonelist,ALLOC_WMARK_LOW|ALLOC_CPUSET);
    //get_page_from_freelist以指定的watermark来分配页面。每个zone struct中定义了三个watermark:pages_min, pages_low, pages_high,表示zone中应保持的空闲页面的阈值。get_page_from_freelist函数通过设置Alloc flags来选择watermark。
    	if (page)//首先以pages_low watermark分配页面,如果分配成功,则跳转到got_pg
    		goto got_pg;
    
    	/*
    	 * GFP_THISNODE (meaning __GFP_THISNODE, __GFP_NORETRY and
    	 * __GFP_NOWARN set) should not cause reclaim since the subsystem
    	 * (f.e. slab) using GFP_THISNODE may choose to trigger reclaim
    	 * using a larger set of nodes after it has established that the
    	 * allowed per node queues are empty and that nodes are
    	 * over allocated.
    	 */
    	if (NUMA_BUILD && (gfp_mask & GFP_THISNODE) == GFP_THISNODE)//如果pages_low watermark分配失败的话,检查gfp_mask,如果GFP_THISNODE标志被设置,表明不能重试,因此跳转到nopage,返回失败goto nopage
    		goto nopage;
    
    	for (z = zonelist->zones; *z; z++)//否则调用kswapd对zonelist中的所有zone进行页面回收,期待能将一些闲置页面交换到文件系统中
    		wakeup_kswapd(*z, order);
    
    	/*
    	 * OK, we're below the kswapd watermark and have kicked background
    	 * reclaim. Now things get more complex, so set up alloc_flags according
    	 * to how we want to proceed.
    	 *
    	 * The caller may dip into page reserves a bit more if the caller
    	 * cannot run direct reclaim, or if the caller has realtime scheduling
    	 * policy or is asking for __GFP_HIGH memory.  GFP_ATOMIC requests will
    	 * set both ALLOC_HARDER (!wait) and ALLOC_HIGH (__GFP_HIGH).
    	 */
    	alloc_flags = ALLOC_WMARK_MIN;//设置alloc_flags的值,以page_min watermark来分配内存
    	if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)//假若进程是非中断处理程序的实时进程,或者该进程不能被阻塞,那么这个时候,我要在最低阈值的标准的基础上,再次降低阈值
    		alloc_flags |= ALLOC_HARDER;
    	if (gfp_mask & __GFP_HIGH))//允许使用保留页面
    		alloc_flags |= ALLOC_HIGH;
    	if (wait)
    		alloc_flags |= ALLOC_CPUSET;
    
    	/*
    	 * Go through the zonelist again. Let __GFP_HIGH and allocations
    	 * coming from realtime tasks go deeper into reserves.
    	 *
    	 * This is the last chance, in general, before the goto nopage.
    	 * Ignore cpuset if GFP_ATOMIC (!wait) rather than fail alloc.
    	 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
    	 */
    	page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);//以指定的watermark来分配页面,详细讨论见下文
    	if (page)//分配成功,就进入got_pg
    		goto got_pg;
    
    	/* This allocation should allow future memory freeing. */
    
    rebalance://上面的第二次分配失败
    	if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
    			&& !in_interrupt()) {//如果当前进程允许本次申请的内存可以被释放,并且不处于软硬中断的状态,我们不顾忌必须保留最小空闲内存页,强行分配
    		if (!(gfp_mask & __GFP_NOMEMALLOC)) {//如果gfp_mask设置不需要保留紧急内存区域,以不设watermark再次分配页面
    nofail_alloc:
    			/* go through the zonelist yet again, ignoring mins */
    			page = get_page_from_freelist(gfp_mask, order,
    				zonelist, ALLOC_NO_WATERMARKS);//以不设watermark进行第三次分配
    			if (page)//第三次分配成功
    				goto got_pg;
    			if (gfp_mask & __GFP_NOFAIL) {//第三次分配失败,如果gfp_mask设置了__GFP_NOFAIL,则不断重试,直到分配成功
    				congestion_wait(WRITE, HZ/50);
    				goto nofail_alloc;
    			}
    		}
    		goto nopage;
    	}
    
    	/* Atomic allocations - we can't balance anything */
    	if (!wait)//原子分配,不允许阻塞,则只能返回失败信号,分配失败
    		goto nopage;
    
    	cond_resched();//重新调度之后,试图释放一些不常用的页面
    
    	/* We now go into synchronous reclaim */
    	cpuset_memory_pressure_bump();//开始进行同步内存回收
    	p->flags |= PF_MEMALLOC;//进程的标志位设置为PF_MEMALLOC
    	reclaim_state.reclaimed_slab = 0;//对于不再活跃的SLAB也给回收掉
    	p->reclaim_state = &reclaim_state;//改变进程回收的状态
    
    	did_some_progress = try_to_free_pages(zonelist->zones, order, gfp_mask);//该函数选择最近不十分活跃的页,将其写到交换区,在物理内存中腾出空间
    
    	p->reclaim_state = NULL;
    	p->flags &= ~PF_MEMALLOC;
    
    	cond_resched();
    
    	if (order != 0)
    		drain_all_local_pages();
    
    	if (likely(did_some_progress)) {//调度之后,如果确实释放了一部分页面,则重新分配页面
    		page = get_page_from_freelist(gfp_mask, order,
    						zonelist, alloc_flags);
    		if (page)
    			goto got_pg;
    	} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {//如果内核可能执行影响VFS层的调用而又没有设置GFP_NORETRY,那么调用OOM killer
    		if (!try_set_zone_oom(zonelist)) {
    			schedule_timeout_uninterruptible(1);
    			goto restart;
    		}
    
    		/*
    		 * Go through the zonelist yet one more time, keep
    		 * very high watermark here, this is only to catch
    		 * a parallel oom killing, we must fail if we're still
    		 * under heavy pressure.
    		 */
    		page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
    				zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
    		if (page) {
    			clear_zonelist_oom(zonelist);
    			goto got_pg;
    		}
    
    		/* The OOM killer will not help higher order allocs so fail */
    		if (order > PAGE_ALLOC_COSTLY_ORDER) {//杀死一个进程未必立即出现多余2^PAGE_ALLOC_CODTLY_ORDER页的连续内存区,因此如果当前要分配如此大的内存区,那么内核会饶恕所选择的进程,不执行杀死进程的任务,而是承认失败并跳转到nopage
    			clear_zonelist_oom(zonelist);
    			goto nopage;
    		}
    
    		out_of_memory(zonelist, gfp_mask, order);//选择一个内核认为犯有分配过多内存“罪行”的进程,并杀死该进程。这有很大几率腾出较多的空闲页,然后跳转到标号restart,重试分配内存的操作
    		clear_zonelist_oom(zonelist);
    		goto restart;
    	}
    
    	/*
    	 * Don't let big-order allocations loop unless the caller explicitly
    	 * requests that.  Wait for some write requests to complete then retry.
    	 *
    	 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
    	 * <= 3, but that may not be true in other implementations.
    	 */
    	//如果设置了__GFP_NORETRY,或内核不允许可能影响VFS层的操作
    	do_retry = 0;
    	if (!(gfp_mask & __GFP_NORETRY)) {//没有设置__GFP_NORETRY
    		if ((order <= PAGE_ALLOC_COSTLY_ORDER) ||
    						(gfp_mask & __GFP_REPEAT))//如果分配长度小于2^PAGE_ALLOC_COSTLY_ORDER或设置了__GFP_REPEAT,则内核进入无限循环
    			do_retry = 1;
    		if (gfp_mask & __GFP_NOFAIL)//如果设置了不允许分配失败,内核也会进入无限循环
    			do_retry = 1;
    	}
    	if (do_retry) {
    		congestion_wait(WRITE, HZ/50);
    		goto rebalance;
    	}
    
    nopage:
    	if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
    		printk(KERN_WARNING "%s: page allocation failure."
    			" order:%d, mode:0x%x\n",
    			p->comm, order, gfp_mask);
    		dump_stack();
    		show_mem();
    	}
    got_pg:
    	return page;
    }

    get_page_from_freelist源代码的详细分析如下:

    static struct page *
    get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
    		struct zonelist *zonelist, int alloc_flags)
    {
    	struct zone **z;//管理区结构体
    	struct page *page = NULL;
    	int classzone_idx = zone_idx(zonelist->zones[0]);//#define zone_idx(zone)        ((zone) - (zone)->zone_pgdat->node_zones) 获取管理区的编号
    	struct zone *zone;
    	nodemask_t *allowednodes = NULL;/* zonelist_cache approximation */
    	int zlc_active = 0;		/* set if using zonelist_cache */
    	int did_zlc_setup = 0;		/* just call zlc_setup() one time */
    	enum zone_type highest_zoneidx = -1; /* Gets set for policy zonelists */
    
    zonelist_scan:
    	/*
    	 * Scan zonelist, looking for a zone with enough free.
    	 * See also cpuset_zone_allowed() comment in kernel/cpuset.c.
    	 */
    	z = zonelist->zones;//让z指向第一个管理区
    	// 在允许的节点中,遍历满足要求的管理区
    	do {
    		/*
    		 * In NUMA, this could be a policy zonelist which contains
    		 * zones that may not be allowed by the current gfp_mask.
    		 * Check the zone is allowed by the current flags
    		 */
    		if (unlikely(alloc_should_filter_zonelist(zonelist))) {//根据zonelist->zlcache_ptr来确定是否需要过滤掉此内存区链表,关于过滤的条件还不是很清楚,请指教
    			if (highest_zoneidx == -1)
    				highest_zoneidx = gfp_zone(gfp_mask);//gfp_zone用于指定分配内存的内存域
    			if (zone_idx(*z) > highest_zoneidx)//首先考虑利用上面指定的内存域,对于一些分配代价高于指定内存域的内存域先不考虑
    				continue;
    		}
    
    		if (NUMA_BUILD && zlc_active &&//是第一遍分配,在其他管理区中分配页面时需要考虑其页面是否充足
    			!zlc_zone_worth_trying(zonelist, z, allowednodes))//该管理区页面不是很充足,考虑下一个管理区
    				continue;
    		zone = *z;
    		if ((alloc_flags & ALLOC_CPUSET) &&
    			!cpuset_zone_allowed_softwall(zone, gfp_mask))//当前分配标志不允许在该管理区中分配页面
    				goto try_next_zone;
    
    		if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {//分配时需要考虑watermark
    			unsigned long mark;//根据分配标志,确定使用哪一个watermark
    			if (alloc_flags & ALLOC_WMARK_MIN)
    				mark = zone->pages_min;
    			else if (alloc_flags & ALLOC_WMARK_LOW)
    				mark = zone->pages_low;
    			else
    				mark = zone->pages_high;
    			if (!zone_watermark_ok(zone, order, mark,
    				    classzone_idx, alloc_flags)) {//该管理区的可用内存不可以满足本次分配的要求
    				if (!zone_reclaim_mode ||//但不满足分配要求时,如果此内存域不能回收内存或者是回收不到可用内存时,就会跳转到this_zone_full
    				    !zone_reclaim(zone, gfp_mask, order))
    					goto this_zone_full;
    			}
    		}
    
    		page = buffered_rmqueue(zonelist, zone, order, gfp_mask);//调用伙伴系统的分配函数
    		if (page)// 从伙伴系统分配成功,退出
    			break;
    this_zone_full:
    		if (NUMA_BUILD)
    			zlc_mark_zone_full(zonelist, z);//标记该管理区空间不足,下次分配时将略过本管理区,避免浪费太多时间
    try_next_zone:
    		if (NUMA_BUILD && !did_zlc_setup) {//当前管理区内存不足,需要加大在其他区中的分配力度
    			/* we do zlc_setup after the first zone is tried */
    			allowednodes = zlc_setup(zonelist, alloc_flags);
    			zlc_active = 1;
    			did_zlc_setup = 1;
    		}
    	} while (*(++z) != NULL);
    
    	if (unlikely(NUMA_BUILD && page == NULL && zlc_active)) {// 第一遍分配不成功,则取消zlc_active,这样会尽量从其他节点中分配内存
    		/* Disable zlc cache for second zonelist scan */
    		zlc_active = 0;
    		goto zonelist_scan;
    	}
    	return page;
    }

    关于上面一段代码中zlc_active的作用不明白,还望理解的人指点一下。

    struct zonelist {
    	struct zonelist_cache *zlcache_ptr;		     // NULL or &zlcache
    	struct zone *zones[MAX_ZONES_PER_ZONELIST + 1];      // NULL delimited
    #ifdef CONFIG_NUMA
    	struct zonelist_cache zlcache;			     // optional ...
    #endif
    };

    struct zonelist_cache {
    	unsigned short z_to_n[MAX_ZONES_PER_ZONELIST];		/* zone->nid */
    	DECLARE_BITMAP(fullzones, MAX_ZONES_PER_ZONELIST);	/* zone full? */
    	unsigned long last_full_zap;		/* when last zap'd (jiffies) */
    };

    zone_watermark_ok源代码详细分析如下:

    int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
    		      int classzone_idx, int alloc_flags)
    {
    	/* free_pages my go negative - that's OK */
    	long min = mark;
    	long free_pages = zone_page_state(z, NR_FREE_PAGES) - (1 << order) + 1;//zone_page_state用来访问每个内存域的统计量,在此处,得到的是空闲页的数目
    	int o;
    
    	if (alloc_flags & ALLOC_HIGH)//设置了ALLOC_HIGH之后,将最小值标记减少一半
    		min -= min / 2;
    	if (alloc_flags & ALLOC_HARDER)//设置了ALLOC_HARDER之后,将最小值标记减少1/4
    		min -= min / 4;
    
    	if (free_pages <= min + z->lowmem_reserve[classzone_idx])//检查空闲页的数目是否小于最小值与lowmem_reserve中制定的紧急分配值之和,如果小于则不进行内存分配
    		return 0;
    	for (o = 0; o < order; o++) {//如果不小于,则代码遍历所有小于当前阶的分配阶
    		/* At the next order, this order's pages become unavailable */
    		free_pages -= z->free_area[o].nr_free << o;//从free_pages减去当前分配阶的所有空闲页
    
    		/* Require fewer higher order pages to be free */
    		min >>= 1;//每升高一阶,所需空闲页的最小值减半,因为阶数越高,每一个块中包含的页面就越多。我们假设初始水线是2^n,那么对阶数0来说,min的值就应当是2^n,对阶数为1来说,min的值就应当除以2变为2^(n-1),因为对于阶数1来说,每个块包含的页面数为2
    
    		if (free_pages <= min)//如果内核遍历所有的低端内存域之后,发现内存不足,则不进行内存分配
    			return 0;
    	}
    	return 1;
    }

    buffered_rmqueue源代码详细分析如下:

    static struct page *buffered_rmqueue(struct zonelist *zonelist,
    			struct zone *zone, int order, gfp_t gfp_flags)
    {
    	unsigned long flags;
    	struct page *page;
    	int cold = !!(gfp_flags & __GFP_COLD);//如果分配参数指定了__GFP_COLD标志,则设置cold标志,两次取反操作确保cold是0或者1,why?请指教
    	int cpu;
    	int migratetype = allocflags_to_migratetype(gfp_flags);//根据gfp_flags获得迁移类型
    
    again:
    	cpu  = get_cpu();//获取本CPU
    	if (likely(order == 0)) {//分配单页,需要管理每CPU页面缓存
    		struct per_cpu_pages *pcp;
    
    		pcp = &zone_pcp(zone, cpu)->pcp[cold];//取得本CPU的页面缓存对象
    		local_irq_save(flags);//这里需要关中断,因为内存回收过程可能发送核间中断,强制每个核从每CPU缓存中释放页面。而且中断处理函数也会分配单页。
    		if (!pcp->count) {//缓存为空,需要扩大缓存的大小
    			pcp->count = rmqueue_bulk(zone, 0,
    					pcp->batch, &pcp->list, migratetype);//从伙伴系统中摘除一批页面到缓存中,补充的页面个数由每CPU缓存的batch字段指定
    			if (unlikely(!pcp->count))//如果缓存仍然为空,那么说明伙伴系统中页面也没有了,分配失败
    				goto failed;
    		}
    
    		/* Find a page of the appropriate migrate type */
    		list_for_each_entry(page, &pcp->list, lru)//遍历每CPU缓存中的所有页,检查是否有指定类型的迁移类型的页可用
    			if (page_private(page) == migratetype)
    				break;
    
    		/* Allocate more to the pcp list if necessary */
    		if (unlikely(&page->lru == &pcp->list)) {
    			pcp->count += rmqueue_bulk(zone, 0,
    					pcp->batch, &pcp->list, migratetype);
    			page = list_entry(pcp->list.next, struct page, lru);
    		}
    
    		list_del(&page->lru);//将页面从每CPU缓存链表中取出,并将每CPU缓存计数减1
    		pcp->count--;
    	} else {
    		spin_lock_irqsave(&zone->lock, flags);
    		page = __rmqueue(zone, order, migratetype);
    		spin_unlock(&zone->lock);
    		if (!page)
    			goto failed;
    	}
    
    	__count_zone_vm_events(PGALLOC, zone, 1 << order);
    	zone_statistics(zonelist, zone);
    	local_irq_restore(flags);
    	put_cpu();
    
    	VM_BUG_ON(bad_range(zone, page));
    	if (prep_new_page(page, order, gfp_flags))
    		goto again;
    	return page;
    
    failed:
    	local_irq_restore(flags);
    	put_cpu();
    	return NULL;
    }

    我也知道有很多的细节都没有分析到位,但是我也没有办法,曾经想着把里面涉及到的每一个函数都分析到位,但是那样的话自己相当的痛苦,因为那样的结果就是很多天都没有办法前进一点,会让人相当的有挫败感,最后只能选择大概先都过一遍,因为自己是一个内核的初学者,而内核前后的关联又很大,也只能先过一遍,到后面我会重新回来看我写得博客,能增进一些分析就增进一些分析。如果您认为上面确实有很重要的地方我没有分析到,希望您指点。





    展开全文
  • 从内核版本2.6.10开始提供一个通用的框架,用于将上述信息转换为伙伴系统预期的结点和内存域数据结构。在这以前,各个体系结构必须自行建立相关结构。现在,体系结构相关代码只需要建立前述的简单结构,将繁重的工作...

    体系结构相关代码需要在启动期间建立以下信息:

    1.系统中各个内存域的页帧边界,保存在max_zone_pfn中

    2.个结点页帧的分配情况,保存在全局变量early_node_map中。

    从内核版本2.6.10开始提供一个通用的框架,用于将上述信息转换为伙伴系统预期的结点和内存域数据结构。在这以前,各个体系结构必须自行建立相关结构。现在,体系结构相关代码只需要建立前述的简单结构,将繁重的工作留给free_area_init_nodes即可。图1给出了该过程概述,图2给出了free_area_init_nodes的代码流程图。


                                                                                            图1:free_area_init_nodes过程概述



                                              图2:free_area_init_nodes代码流程图

    free_area_init_nodes的源代码的详细分析如下:

    void __init free_area_init_nodes(unsigned long *max_zone_pfn)
    {
    	unsigned long nid;
    	enum zone_type i;
    
    	/* Sort early_node_map as initialisation assumes it is sorted */
    	sort_node_map();//排序使得后续的任务稍微容易些,排序本身并不特别复杂
    
    	/* Record where the zone boundaries are */
    	memset(arch_zone_lowest_possible_pfn, 0,
    				sizeof(arch_zone_lowest_possible_pfn));//全局数组arch_zone_lowest_possible_pfn用来存储各个内存域可使用的最低内存页帧编号
    	memset(arch_zone_highest_possible_pfn, 0,
    			sizeof(arch_zone_highest_possible_pfn));//全局数组arch_zone_highest_possible_pfn用来存储各个内存域可使用的最高内存页帧编号
    	arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();//辅助函数find_min_pfn_with_active_regions用于找到注册的最低内存域中可用的编号最小的页帧
    
    	arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];//max_zone_pfn记录了各个内存域包含的最大页帧号
    	for (i = 1; i < MAX_NR_ZONES; i++) {//依次遍历,确定各个内存域的边界
    		if (i == ZONE_MOVABLE)//由于ZONE_MOVABLE是一个虚拟内存域,不与真正的硬件内存域关联,该内存域的边界总是设置为0,如后面的代码所示
    			continue;
    		arch_zone_lowest_possible_pfn[i] =
    			arch_zone_highest_possible_pfn[i-1];//第n个内存域的最小页帧,即前一个(第n-1个)内存域的最大页帧
    		arch_zone_highest_possible_pfn[i] =
    			max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);//不出意外,当前内存域的最大页帧由max_zone_pfn给出
    	}
    	arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;
    	arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;
    
    	/* Find the PFNs that ZONE_MOVABLE begins at in each node */
    	memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
    	find_zone_movable_pfns_for_nodes(zone_movable_pfn);//用于计算进入ZONE_MOVABLE的内存数量,详细分析见下文
    
    	/* Print out the zone ranges */
    	printk("Zone PFN ranges:\n");
    	for (i = 0; i < MAX_NR_ZONES; i++) {//将各个内存域的最大、最小页帧号显示出来
    		if (i == ZONE_MOVABLE)
    			continue;
    		printk("  %-8s %8lu -> %8lu\n",
    				zone_names[i],
    				arch_zone_lowest_possible_pfn[i],
    				arch_zone_highest_possible_pfn[i]);
    	}
    
    	/* Print out the PFNs ZONE_MOVABLE begins at in each node */
    	printk("Movable zone start PFN for each node\n");
    	for (i = 0; i < MAX_NUMNODES; i++) {
    		if (zone_movable_pfn[i])//对每个结点来说,zone_movable_pfn[node_id]表示ZONE_MOVABLE在movable_zone内存域中所取得内存的起始地址。内核确保这些页将用于满足符合ZONE_MOVABLE职责的内存分配
    			printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);
    	}
    
    	/* Print out the early_node_map[] */
    	printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);
    	for (i = 0; i < nr_nodemap_entries; i++)//显示各个内存域的分配情况
    		printk("  %3d: %8lu -> %8lu\n", early_node_map[i].nid,
    						early_node_map[i].start_pfn,
    						early_node_map[i].end_pfn);
    
    	/* Initialise every node */
    	setup_nr_node_ids();
    	for_each_online_node(nid) {//代码遍历所有的活动结点,并分别对各个结点调用free_area_init_node建立数据结构,该函数需要结点第一个可用的页帧作为一个参数,而find_min_pfn_for_node则从early_node_map数组提取该信息
    		pg_data_t *pgdat = NODE_DATA(nid);
    		free_area_init_node(nid, pgdat, NULL,
    				find_min_pfn_for_node(nid), NULL);
    
    		/* Any memory on that node */
    		if (pgdat->node_present_pages)//根据node_present_pages字段判断结点具有内存,则在结点位图中设置N_HIGH_MEMORY标志,该标志只表示结点上存在普通或高端内存,因此check_for_regular_memory进一步检查低于ZONE_HIGHMEM的内存域中是否有内存,并据此在结点位图中相应地设置N_NORMAL_MEMORY
    			node_set_state(nid, N_HIGH_MEMORY);
    		check_for_regular_memory(pgdat);
    	}
    }

    free_area_init_node源代码详细分析:

    void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,
    		unsigned long *zones_size, unsigned long node_start_pfn,
    		unsigned long *zholes_size)
    {
    	pgdat->node_id = nid;
    	pgdat->node_start_pfn = node_start_pfn;
    	calculate_node_totalpages(pgdat, zones_size, zholes_size);//首先累计各个内存域的页数,计算结点中页的总数。对连续内存模型而言,这可以通过zone_sizes_init完成,但calculate_node_totalpages还考虑了内存空洞
    
    	alloc_node_mem_map(pgdat);//分配了该节点的页面描述符数组[pgdat->node_mem_map数组的内存分配] 
    
    	free_area_init_core(pgdat, zones_size, zholes_size);//对该节点的每个区[DMA,NORMAL,HIGH]的的结构进行初始化
    }
    calculate_node_totalpages源代码详细分析:

    static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,
    		unsigned long *zones_size, unsigned long *zholes_size)
    {
    	unsigned long realtotalpages, totalpages = 0;
    	enum zone_type i;
    
    	for (i = 0; i < MAX_NR_ZONES; i++)
    		totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,
    								zones_size);//累计计算各个内存域包含空洞的内存总页数
    	pgdat->node_spanned_pages = totalpages;
    
    	realtotalpages = totalpages;
    	for (i = 0; i < MAX_NR_ZONES; i++)
    		realtotalpages -=
    			zone_absent_pages_in_node(pgdat->node_id, i,
    								zholes_size)//;以包含空洞的内存总页数累计减去各个内存域中空洞的数量,就可以得出实际可用的内存页数
    	pgdat->node_present_pages = realtotalpages;
    	printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,
    							realtotalpages);
    }
    alloc_node_mem_map源代码详细分析:

    static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)
    {
    	/* Skip empty nodes */
    	if (!pgdat->node_spanned_pages)//如果内存结点没有没存页,直接返回
    		return;
    
    #ifdef CONFIG_FLAT_NODE_MEM_MAP
    	/* ia64 gets its own node_mem_map, before this, without bootmem */
    	if (!pgdat->node_mem_map) {//如果还没有为结点分配mem_map,则需要为结点分配mem_map
    		unsigned long size, start, end;
    		struct page *map;
    
    		/*
    		 * The zone's endpoints aren't required to be MAX_ORDER
    		 * aligned but the node_mem_map endpoints must be in order
    		 * for the buddy allocator to function correctly.
    		 */
    		start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);//确定起点,以MAX_ORDER_NR_PAGES的大小对齐
    		end = pgdat->node_start_pfn + pgdat->node_spanned_pages;//计算结束点
    		end = ALIGN(end, MAX_ORDER_NR_PAGES);//以MAX_ORDER_NR_PAGES对齐,与上面的功能一致,将内存映射对齐到伙伴系统的最大分配阶
    		size =  (end - start) * sizeof(struct page);//计算所需内存的大小
    		map = alloc_remap(pgdat->node_id, size);//为内存映射分配内存
    		if (!map)//如果分配不成功,则使用普通的自举内存分配器进行分配
    			map = alloc_bootmem_node(pgdat, size);
    		pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);
    	}
    #ifndef CONFIG_NEED_MULTIPLE_NODES
    	/*
    	 * With no DISCONTIG, the global mem_map is just set as node 0's
    	 */
    	if (pgdat == NODE_DATA(0)) {
    		mem_map = NODE_DATA(0)->node_mem_map;
    #ifdef CONFIG_ARCH_POPULATES_NODE_MAP
    		if (page_to_pfn(mem_map) != pgdat->node_start_pfn)
    			mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);
    #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */
    	}
    #endif
    #endif /* CONFIG_FLAT_NODE_MEM_MAP */
    }
    

    free_area_init_core源代码详细分析:

    static void __meminit free_area_init_core(struct pglist_data *pgdat,
    		unsigned long *zones_size, unsigned long *zholes_size)
    {
    	enum zone_type j;
    	int nid = pgdat->node_id;
    	unsigned long zone_start_pfn = pgdat->node_start_pfn;
    	int ret;
    
    	pgdat_resize_init(pgdat);
    	pgdat->nr_zones = 0;
    	init_waitqueue_head(&pgdat->kswapd_wait);
    	pgdat->kswapd_max_order = 0;
    	
    	for (j = 0; j < MAX_NR_ZONES; j++) {
    		struct zone *zone = pgdat->node_zones + j;
    		unsigned long size, realsize, memmap_pages;
    
    		size = zone_spanned_pages_in_node(nid, j, zones_size);//内存域跨域的页数
    		realsize = size - zone_absent_pages_in_node(nid, j,
    								zholes_size);//内存域的可用长度,可通过跨域的页数减去空洞覆盖的页数而得到
    
    		/*
    		 * Adjust realsize so that it accounts for how much memory
    		 * is used by this zone for memmap. This affects the watermark
    		 * and per-cpu initialisations
    		 */
    		memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;//用于内存映射需要的页数
    		if (realsize >= memmap_pages) {如果内存域的可用长度大于用于内存映射需要的页数
    			realsize -= memmap_pages;//则将需要映射的页数分配出去
    			printk(KERN_DEBUG
    				"  %s zone: %lu pages used for memmap\n",
    				zone_names[j], memmap_pages);
    		} else//否则,显示警告信息,可用内存不足
    			printk(KERN_WARNING
    				"  %s zone: %lu pages exceeds realsize %lu\n",
    				zone_names[j], memmap_pages, realsize);
    
    		/* Account for reserved pages */
    		if (j == 0 && realsize > dma_reserve) {
    			realsize -= dma_reserve;
    			printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",
    					zone_names[0], dma_reserve);
    		}//除去用于保留的内存页
    
    		if (!is_highmem_idx(j))
    			nr_kernel_pages += realsize;//nr_kernel_pages表示不包含高端内存的系统内存共有的内存页面数,用于统计所有一致映射的页
    		nr_all_pages += realsize;
    
    		zone->spanned_pages = size;//跨域的内存页
    		zone->present_pages = realsize;//经过一系列初始化之后,还可使用的内存页
    #ifdef CONFIG_NUMA
    		zone->node = nid;
    		zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)/ 100;//这句话不理解,请指教
    		zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;//这句话不理解,请指教
    #endif
    		zone->name = zone_names[j];
    		spin_lock_init(&zone->lock);//关于锁机制,自己还没有学到,后面会详细介绍锁机制
    		spin_lock_init(&zone->lru_lock);
    		zone_seqlock_init(zone);
    		zone->zone_pgdat = pgdat;
    
    		zone->prev_priority = DEF_PRIORITY;
    
    		zone_pcp_init(zone);//初始化该内存域的per_cpu缓存
    		INIT_LIST_HEAD(&zone->active_list);
    		INIT_LIST_HEAD(&zone->inactive_list);
    		zone->nr_scan_active = 0;
    		zone->nr_scan_inactive = 0;
    		zap_zone_vm_stats(zone);
    		zone->flags = 0;
    		if (!size)
    			continue;
    
    		set_pageblock_order(pageblock_default_order());
    		setup_usemap(pgdat, zone, size);
    		ret = init_currently_empty_zone(zone, zone_start_pfn,
    						size, MEMMAP_EARLY);//init_currently_empty_zone用于初始化free_area列表,并将属于该内存域的所有page实例都设置为初始默认值
    		BUG_ON(ret);
    		zone_start_pfn += size;
    	}
    }
    
    check_for_regular_memory源代码详细分析:

    static void check_for_regular_memory(pg_data_t *pgdat)
    {
    #ifdef CONFIG_HIGHMEM
    	enum zone_type zone_type;
    
    	for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {//进一步检查低于ZONE_HIGHMEM的内存域中是否有内存
    
    		struct zone *zone = &pgdat->node_zones[zone_type];
    		if (zone->present_pages)
    			node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);//并根据上面的检查在结点位图中相应地设置N_NORMAL_MEMORY
    
    	}
    #endif
    }

    我也知道有很多的细节都没有分析到位,但是我也没有办法,曾经想着把里面涉及到的每一个函数都分析到位,但是那样的话自己相当的痛苦,因为那样的结果就是很多天都没有办法前进一点,会让人相当的有挫败感,最后只能选择大概先都过一遍,因为自己是一个内核的初学者,而内核前后的关联又很大,也只能先过一遍,到后面我会重新回来看我写得博客,能增进一些分析就增进一些分析。如果您认为上面确实有很重要的地方我没有分析到,希望您指点。





    展开全文
  • 内存管理伙伴算法

    2013-12-25 11:07:27
    内存管理伙伴算法
  • 内存管理算法--Buddy伙伴算法

    千次阅读 2015-12-01 15:29:34
    Buddy算法的优缺点:1)尽管伙伴内存...2)算法中有一定的浪费现象,伙伴算法是按2的幂次方大小进行分配内存块,当然这样做是有原因的,即为了避免把大的内存块拆的太碎,更重要的是使分配和释放过程迅速。但是他也带来

    Buddy算法的优缺点:

    1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放,旁边两个大的就不能合并。

    2)算法中有一定的浪费现象,伙伴算法是按2的幂次方大小进行分配内存块,当然这样做是有原因的,即为了避免把大的内存块拆的太碎,更重要的是使分配和释放过程迅速。但是他也带来了不利的一面,如果所需内存大小不是2的幂次方,就会有部分页面浪费。有时还很严重。比如原来是1024个块,申请了16个块,再申请600个块就申请不到了,因为已经被分割了。

    3)另外拆分和合并涉及到 较多的链表和位图操作,开销还是比较大的。

    Buddy(伙伴的定义):

    这里给出伙伴的概念,满足以下三个条件的称为伙伴:
    1)两个块大小相同;
    2)两个块地址连续;
    3)两个块必须是同一个大块中分离出来的;

    Buddy算法的分配原理:

    假如系统需要4(2*2)个页面大小的内存块,该算法就到free_area[2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去。如果没有,算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,free_area[3]中也没有,就再向上查找,如果free_area[4]中有,就将这16(2*2*2*2)个页面等分成两份,前一半挂如free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]
    的链表中,后一半分配出去。假如free_area[4]也没有,则重复上面的过程,知道到达free_area数组的最后,如果还没有则放弃分配。



    Buddy算法的释放原理:

    内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块时,先在其对应的链表中考查是否有伙伴存在,如果没有伙伴块,就直接把要释放的块挂入链表头;如果有,则从链表中摘下伙伴,合并成一个大块,然后继续考察合并后的块在更大一级链表中是否有伙伴存在,直到不能合并或者已经合并到了最大的块(2*2*2*2*2*2*2*2*2个页面)。


    整个过程中,位图扮演了重要的角色,如图2所示,位图的某一位对应两个互为伙伴的块,为1表示其中一块已经分配出去了,为0表示两块都空闲。伙伴中无论是分配还是释放都只是相对的位图进行异或操作。分配内存时对位图的
    是为释放过程服务,释放过程根据位图判断伙伴是否存在,如果对相应位的异或操作得1,则没有伙伴可以合并,如果异或操作得0,就进行合并,并且继续按这种方式合并伙伴,直到不能合并为止。

    参考文献:

    http://blog.csdn.net/orange_os/article/details/7392986

    http://blog.csdn.net/zhongnanjun_3/article/details/21799209

    http://www.oschina.net/code/snippet_180916_7598


    展开全文
  • 内存管理算法--伙伴算法

    千次阅读 2015-02-22 23:36:19
    本来想年前就把内存管理这部分结束,可是计划赶不上变化啊,回家事情太多,只能一拖再拖了,今天终于把伙伴算法机制写完了。这一节不再像前面似的只给出理论框架,毕竟linux内存管理的两个算法--伙伴算法和slab网上...
  • 详细描述了linux内存管理中伙伴算法的技术原理,对了解内存管理很有帮助
  •   提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。...伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当...
  • 内存分配算法代码模拟。包含 首次适应算法(First Fit) 最佳适应算法(Best Fit)最差适应算法(Worst Fit)伙伴算法(buddy) https://blog.csdn.net/GreyBtfly/article/details/84646981
  • 内存分配算法之伙伴算法

    千次阅读 2011-03-21 18:13:00
    Next Fit算法 首先为了作一个对比,使用了一个来自于《C程序设计语言》上面的malloc版本来进行比对。 这个简单版本的思想是使用一个循环单链表来进行空闲块的维护,base变量表示该链表的头,freep表示上次操作的
  • 内存管理之伙伴算法

    2019-09-16 19:27:17
    算法作用 它要解决的问题是频繁地请求和释放不同大小的... 伙伴算法(Buddy system)把所有的空闲页框分为11个块链表,每块链表中分布包含特定的连续页框地址空间,比如第0个块链表包含大小为2^0个连续的页框,第...
  • 本节,我将介绍linux系统物理内存分配时所用到的技术——伙伴系统和slab缓存。 伙伴系统 使用场景:内核中很多时候要求分配连续页,为快速检测内存中的连续区域,内核采用了一种技术:伙伴系统。 原理:系统中...
  • 伙伴算法内存管理

    2015-02-09 14:26:59
    基于Ucosii改进的具有伙伴算法内存管理
  • 分区分配算法:  首次适应算法(First Fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给 作业,这种方法的目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲...
  • C#图形界面,基于linux伙伴算法,对虚拟内存管理。包含可视化窗格,界面简单易懂
  • 内存管理问题: 内存碎片大小和管理内存碎片的效率问题(即空间和时间效率的问题): 内存碎片是指当回收一块内存时,一般将内存直接放入free链表中,由于内存越分配越小,内存块就会特别多...2.伙伴算法. 3.slab算法. ...
  • 内存管理伙伴算法 模拟程序

    千次阅读 2014-06-13 15:30:26
    cout 空闲内存伙伴算法程序模拟" ; cout 初始化内存分配" ; cout 作业分配申请内存" ; cout 作业释放内存" ; cout 查看当前内存使用情况" ; cout 退出模拟程序" ; } //获得要初始化的内存大小 bool ...
  • 伙伴算法和slab算法 slab机制 slab机制总结篇 总结: 内部碎片和外部碎片: 内部碎片的产生: 因为所有的内存分配必须起始于可被 4、8 或 16 整除(视处理器体系结构而定)的地址或者因为MMU的分页机制的限制, ...
  • 内存碎片及伙伴算法

    2018-04-02 20:24:40
    今天学习到 Linux 内存分配问题,有些不明白,什么是内存碎片问题?以及为什么maloc()等函数每次分配内存后都会用 free()释放资源,为什么还会产生碎片问题?内存碎片问题如何产生 及 如何解决呢?以下是自己...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,535
精华内容 12,214
关键字:

内存伙伴算法