Linux Buddy系统算法源码解析收藏
在Linux引导起来之后,伙伴系统分配算法是和物理内存最底层的接口。所有内存分配函数,比如vmalloc/kmalloc最后都是通过伙伴算法对内存进行分配的。接下来我们将解读一下伙伴系统的分配和回收算法。 伙伴系统模块提供了两个主要的接口给上层程序,他们是: 1. 页面请求函数 struct page * fastcall __alloc_pages(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist) 2. 页面释放函数 fastcall void __free_pages(struct page *page, unsigned int order) 【注】:在这里我对fastcall进行说明一下,他指明了函数参数传递的方式,前8个字节通过寄存器传入,后面多出来的通过栈传入,入栈顺序是从右到左。 下面分别对两个函数进行源码级的分析。 1. 页面分配 a) 如果请求的内存大小正好是一个页面,则需要从该CPU的冷热页面队列中进行分配。 if (likely(order == 0)) { struct per_cpu_pages *pcp; pcp = &zone_pcp(zone, cpu)->pcp[cold]; // 获取冷热页面队列的指针。 local_irq_save(flags); if (!pcp->count) { // 如果发现页面队列中的页面数为0,需要从伙伴系统中申请一组页面,填充页面队列。 pcp->count += rmqueue_bulk(zone, 0, pcp->batch, &pcp->list); if (unlikely(!pcp->count)) goto failed; } // 从队列中取出一页分配出去 page = list_entry(pcp->list.next, struct page, lru); list_del(&page->lru); // 计数器减一 pcp->count--; } b) 如果申请的物理内存大于1个页面,直接从伙伴系统中申请 spin_lock_irqsave(&zone->lock, flags); page = __rmqueue(zone, order); // 访问伙伴系统 spin_unlock(&zone->lock); if (!page) goto failed; c) 对刚才分配的页面进行一系列的检查。检查失败需要重新从伙伴系统进行分配。并且对该页面进行相应的初始化。 if (prep_new_page(page, order)) goto again; d) 是否需要对页面进行清零操作 if (gfp_flags & __GFP_ZERO) prep_zero_page(page, order, gfp_flags); e) 如果从伙伴系统中申请的页面不是一个页面,即order > 1,我们称之为一个compound页面。下面需要初始化compound页面。通过设置页面的标志位来表示他是一个compound页面。 set_bit(PG_compound, &(page)->flags) f) 如果以上过程页面分配成功,则完成分配,如果不成功,继续下面的尝试。 g) 将kswapd内核线程唤醒,换出一些页面。 do { wakeup_kswapd(*z, order); } while (*(++z)); h) 从伙伴系统中,尝试再次分配页面。 page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags); if (page) goto got_pg; i) 如果发现该任务是专用于分配内存的(PF_MEMALLOC)并且不处于中断处理函数中,则强制性的分配内存,也就是说不管有没有到每个内存区的地水位线,都给他分配,除非是真的没得分配了。 if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) && !in_interrupt()) { if (!(gfp_mask & __GFP_NOMEMALLOC)) { nofail_alloc: /* go through the zonelist yet again, ignoring mins */ page = get_page_from_freelist(gfp_mask, order, zonelist, ALLOC_NO_WATERMARKS); if (page) goto got_pg; if (gfp_mask & __GFP_NOFAIL) { blk_congestion_wait(WRITE, HZ/50); goto nofail_alloc; } } goto nopage; // 表示没有页面可以分配了。 } j) 如果不是特殊任务,则系统尝试将各个区的内存进行一个rebalance的动作,就是回收些内存。 did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask); 然后在尝试分配: page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags); if (page) goto got_pg; 如果分配失败,就终止请求页面的进程。 out_of_memory(zonelist, gfp_mask, order); 我们接下来分析一下从伙伴系统申请页面的函数。 static struct page *__rmqueue(struct zone *zone, unsigned int order) 从空闲表中当前order进行查找,找到第一个有空闲块的order,叫做current_order,然后进行分配,有两种情况,第一种情况:刚好current_order就是请求的order,则不需要合并。第二种情况:current_order是大于请求的order的,这种情况,是需要进行页面块的拆分和合并的。调用expand函数。通过设置相邻页面的PG_buddy位来表示他们是伙伴。 for (current_order = order; current_order < MAX_ORDER; ++current_order) { area = zone->free_area + current_order; if (list_empty(&area->free_list)) continue; page = list_entry(area->free_list.next, struct page, lru); list_del(&page->lru); rmv_page_order(page); area->nr_free--; zone->free_pages -= 1UL << order; expand(zone, page, order, current_order, area); return page; } 2. 页面释放 fastcall void __free_pages(struct page *page, unsigned int order) a) 先测试该页面的引用计数器是不是为1,否则不能释放,因为其他进程可能引用了该页面。 if (put_page_testzero(page)) b) 如果释放的页面为1,则释放到热页面队列中去。否则直接释放到伙伴系统中去。 if (order == 0) free_hot_page(page); else __free_pages_ok(page, order); 接下来我们分析一下释放一个页面到伙伴系统的代码: static inline void __free_one_page(struct page *page, struct zone *zone, unsigned int order) 1. 如果是compound页面,先清除页面标志位PG_compound。 if (unlikely(PageCompound(page))) destroy_compound_page(page, order); 2. 查找伙伴块,并对伙伴块进行合并,最后将合并后的块插入到新的order中去。这个过程一直持续下去,直到伙伴块合并完为止。 while (order < MAX_ORDER-1) { unsigned long combined_idx; struct free_area *area; struct page *buddy; buddy = __page_find_buddy(page, page_idx, order); if (!page_is_buddy(buddy, order)) break; /* Move the buddy up one level. */ list_del(&buddy->lru); area = zone->free_area + order; area->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++; }
|
|
来自: jijo > 《slab/slub/kmalloc》