摘要:本文主要讲述linux如何处理ARM cortex A9多核处理器的内存管理部分。主要包括对伙伴系统算法流程的介绍。
法律声明:《LINUX3.0内核源代码分析》系列文章由谢宝友()发表于http://xiebaoyou.blog.chinaunix.net,文章中的LINUX3.0源代码遵循GPL协议。除此以外,文档中的其他内容由作者保留所有版权。谢绝转载。
1.1.1 伙伴系统 1.1.1.1 从缓存中释放单个页面到伙伴系统
当释放单个页面时,页面首先放回到每CPU的页面缓存中,以减少自旋锁的使用。当页面缓存中的页面数量超过阀值时,再将页面放回到伙伴系统中。相应的函数是free_pcppages_bulk:
- /**
- * 从每CPU缓存中释放一定数量的页面到伙伴系统中。
- */
- static void free_pcppages_bulk(struct zone *zone, int count,
- struct per_cpu_pages *pcp)
- {
- int migratetype = 0;
- int batch_free = 0;
- int to_free = count;
- /**
- * 虽然管理区可以按照CPU节点分类,但是也可以跨CPU节点进行内存分配,因此这里需要用自旋锁保护管理区
- * 使用每CPU缓存的目的,也是为了减少使用这把锁。
- */
- spin_lock(&zone->lock);
- /* all_unreclaimable代表了内存紧张程度,释放内存后,将此标志清除 */
- zone->all_unreclaimable = 0;
- zone->pages_scanned = 0;/* pages_scanned代表最后一次内存紧张以来,页面回收过程已经扫描的页数。目前正在释放内存,将此清0,待回收过程随后回收时重新计数 */
- while (to_free) {/* 连续释放指定数量的页面到伙伴系统 */
- struct page *page;
- struct list_head *list;
- /* 这里是从MIGRATE_UNMOVABLE到MIGRATE_MOVABLE三个每CPU缓存链表中依次搜索一个可释放的页面,直到找到一个可以回收的缓存链表。 */
- do {
- batch_free++;/* batch_free是最后扫描的链表索引 */
- if (++migratetype == MIGRATE_PCPTYPES)/* 只从MIGRATE_UNMOVABLE..MIGRATE_MOVABLE三个链表中选择页面。从这三个链表中循环选择回收的页面 */
- migratetype = 0;
- list = &pcp->lists[migratetype];
- } while (list_empty(list));/* 如果当前链表为空,则从下一个缓存链表中释放页面 */
- /* This is the only non-empty list. Free them all. */
- if (batch_free == MIGRATE_PCPTYPES)/* 只有一个缓存链表中有可回收页面,则从该链表中释放所有页面 */
- batch_free = to_free;
- do {/* 本循环从最后一个页面缓存链表中释放多个页面到伙伴系统,越靠后的缓存链表,释放的页面数量越多 */
- page = list_entry(list->prev, struct page, lru);/* 取缓存链表的最后一个元素,要么是最早放到缓存中的页面(其硬件缓存的热度也最低),要么就是"冷"页,不需要考虑硬件缓存 */
- /* must delete as __free_one_page list manipulates */
- list_del(&page->lru);/* 将页面从链表中摘除 */
- /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
- /* 将页面释放回伙伴系统。注意这里没有用migratetype变量,而是用页面属性中的migratetype。原因请参见英文注释 */
- __free_one_page(page, zone, 0, page_private(page));
- trace_mm_page_pcpu_drain(page, 0, page_private(page));/* 调试代码 */
- } while (--to_free && --batch_free && !list_empty(list));
- }
- /* 空闲页面计数 */
- __mod_zone_page_state(zone, NR_FREE_PAGES, count);
- spin_unlock(&zone->lock);
- }
1.1.1.2 释放多个页面到伙伴系统
一次性分配和释放多个页面,都不经过每CPU缓存,而是直接从伙伴系统中分配、直接返回给伙伴系统。
向伙伴系统释放页面的函数是free_one_page,这个函数有点名不副实。它并不是指释放一个页面,而是释放多个页面,不知道内核为何取如此奇怪的名字。
- /**
- * 将多个页面释放到伙伴系统。
- */
- static void free_one_page(struct zone *zone, struct page *page, int order,
- int migratetype)
- {
- spin_lock(&zone->lock);/* 获得管理区的自旋锁 */
- zone->all_unreclaimable = 0;/* 只要是释放了页面,都需要将此两个标志清0,表明内存不再紧张的事实 */
- zone->pages_scanned = 0;
- /* 在锁的保护下,调用__free_one_page操作伙伴系统,将页面释放回伙伴系统 */
- __free_one_page(page, zone, order, migratetype);
- /* 管理区空闲页面计数 */
- __mod_zone_page_state(zone, NR_FREE_PAGES, 1 << order);
- spin_unlock(&zone->lock);/* 释放管理区自旋锁 */
- }
在获得管理区锁的情况下,不管是释放一个页还是多个页到伙伴系统,均使用函数__free_one_page:
- /**
- * 在获得管理区自旋锁的情况下,将页面归还给伙伴系统。
- */
- static inline void __free_one_page(struct page *page,
- struct zone *zone, unsigned int order,
- int migratetype)
- {
- unsigned long page_idx;
- unsigned long combined_idx;
- unsigned long uninitialized_var(buddy_idx);
- struct page *buddy;
- if (unlikely(PageCompound(page)))/* 要释放的页是巨页的一部分 */
- if (unlikely(destroy_compound_page(page, order)))/* 解决巨页标志,如果巨页标志有问题,则退出 */
- return;
- VM_BUG_ON(migratetype == -1);
- page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
- VM_BUG_ON(page_idx & ((1 << order) - 1));/* 如果被释放的页不是所释放阶的第一个页,则说明参数有误 */
- VM_BUG_ON(bad_range(zone, page));/* 检查页面是否处于zone之中 */
- while (order < MAX_ORDER-1) {/* 释放页以后,当前页面可能与前后的空闲页组成更大的空闲页面,直到放到最大阶的伙伴系统中 */
- buddy_idx = __find_buddy_index(page_idx, order);/* 找到与当前页属于同一个阶的伙伴页面索引 */
- buddy = page + (buddy_idx - page_idx);/* 计算伙伴页面的页地址 */
- if (!page_is_buddy(page, buddy, order))/* 判断预期的伙伴页面是否与当前页处于同一个管理区,并且是否处于空闲状态。如果不是,则不能与该页合并为大的伙伴,退出 */
- break;
- /* Our buddy is free, merge with it and move up one order. */
- list_del(&buddy->lru);/* 如果能够合并,则将伙伴页从伙伴系统中摘除 */
- zone->free_area[order].nr_free--;/* 同时减少当前阶中的空闲页计数 */
- rmv_page_order(buddy);/* 清除伙伴页的伙伴标志,因为该页会被合并 */
- combined_idx = buddy_idx & page_idx;
- /* 将当前页与伙伴页合并后,新的页面起始地址 */
- page = page + (combined_idx - page_idx);
- page_idx = combined_idx;
- order++;
- }
- /* 设置伙伴页中第一个空闲页的阶 */
- set_page_order(page, order);
- /**
- * 如果当前合并后的页不是最大阶的,那么将当前空闲页放到伙伴链表的最后。
- * 这样,它将不会被很快被分配,更有可能与更高阶页面进行合并。
- */
- if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
- struct page *higher_page, *higher_buddy;
- /* 计算更高阶的页面索引及页面地址 */
- combined_idx = buddy_idx & page_idx;
- higher_page = page + (combined_idx - page_idx);
- buddy_idx = __find_buddy_index(combined_idx, order + 1);
- higher_buddy = page + (buddy_idx - combined_idx);
- if (page_is_buddy(higher_page, higher_buddy, order + 1)) {/* 更高阶的页面是空闲的,属于伙伴系统 */
- list_add_tail(&page->lru,
- &zone->free_area[order].free_list[migratetype]);/* 将当前页面合并到空闲链表的最后,尽量避免将它分配出去 */
- goto out;
- }
- }
- /* 更高阶的页面已经分配出去,那么将当前页面放到链表前面 */
- list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
- out:
- /* 将当前阶的空闲计数加1 */
- zone->free_area[order].nr_free++;
- }
1.1.1.3 从伙伴系统中获得页面
从伙伴系统中分配页面的函数是buffered_rmqueue:
- /**
- * 从伙伴系统中分配页面
- */
- static inline
- struct page *buffered_rmqueue(struct zone *preferred_zone,
- struct zone *zone, int order, gfp_t gfp_flags,
- int migratetype)
- {
- unsigned long flags;
- struct page *page;
- int cold = !!(gfp_flags & __GFP_COLD);/* 如果分配参数指定了__GFP_COLD标志,则设置cold标志 */
- again:
- if (likely(order == 0)) {/* 分配单页,需要管理每CPU页面缓存 */
- struct per_cpu_pages *pcp;
- struct list_head *list;
- /* 这里需要关中断,因为内存回收过程可能发送核间中断,强制每个核从每CPU缓存中释放页面。而且中断处理函数也会分配单页。 */
- local_irq_save(flags);
- /* 取得本CPU的页面缓存对象 */
- pcp = &this_cpu_ptr(zone->pageset)->pcp;
- /* 根据用户指定的迁移类型,从指定的迁移缓存链表中分配 */
- list = &pcp->lists[migratetype];
- if (list_empty(list)) {/* 缓存为空,需要扩大缓存的大小 */
- /* 从伙伴系统中摘除一批页面到缓存中,补充的页面个数由每CPU缓存的batch字段指定 */
- pcp->count += rmqueue_bulk(zone, 0,
- pcp->batch, list,
- migratetype, cold);
- /* 如果链表仍然为空,那么说明伙伴系统中页面也没有了,分配失败。 */
- if (unlikely(list_empty(list)))
- goto failed;
- }
- if (cold)
- /* 如果分配的页面不需要考虑硬件缓存(注意不是每CPU页面缓存),则取出链表的最后一个节点返回给上层 */
- page = list_entry(list->prev, struct page, lru);
- else
- /* 如果要考虑硬件缓存,则取出链表的第一个页面,这个页面是最近刚释放到每CPU缓存的,缓存热度更高 */
- page = list_entry(list->next, struct page, lru);
- /* 将页面从每CPU缓存链表中取出,并将每CPU缓存计数减1 */
- list_del(&page->lru);
- pcp->count--;
- } else {/* 分配的是多个页面,不需要考虑每CPU页面缓存,直接从系统中分配 */
- if (unlikely(gfp_flags & __GFP_NOFAIL)) {/* __GFP_NOFAIL已经不推荐使用,不再分析 */
- /*
- * __GFP_NOFAIL is not to be used in new code.
- *
- * All __GFP_NOFAIL callers should be fixed so that they
- * properly detect and handle allocation failures.
- *
- * We most definitely don't want callers attempting to
- * allocate greater than order-1 page units with
- * __GFP_NOFAIL.
- */
- WARN_ON_ONCE(order > 1);
- }
- /* 关中断,并获得管理区的锁 */
- spin_lock_irqsave(&zone->lock, flags);
- /* 调用__rmqueue从伙伴系统中分配页面 */
- page = __rmqueue(zone, order, migratetype);
- /* 这里仅仅打开自旋锁,待后面统计计数设置完毕后再开中断 */
- spin_unlock(&zone->lock);
- if (!page)
- goto failed;
- /* 已经分配了1 << order个页面,这里进行管理区空闲页面统计计数 */
- __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order));
- }
- /* 事件统计计数,调试用 */
- __count_zone_vm_events(PGALLOC, zone, 1 << order);
- zone_statistics(preferred_zone, zone, gfp_flags);
- local_irq_restore(flags);/* 恢复中断 */
- VM_BUG_ON(bad_range(zone, page));
- /**
- * 这里进行安全性检查,并进行一些善后工作。
- * 如果页面标志破坏,返回的页面出现了问题,则返回试图分配其他页面。
- * 内核会有这样的BUG存在吗?除了驱动或者模块有问题外?
- */
- if (prep_new_page(page, order, gfp_flags))
- goto again;
- return page;
- failed:
- local_irq_restore(flags);
- return NULL;
- }
这里使用了一个辅助函数rmqueue_bulk:
- /**
- * 从伙伴系统中批量取出多个页面。
- * 用于从伙伴系统中批量取出页面放到每CPU页面缓存中
- */
- static int rmqueue_bulk(struct zone *zone, unsigned int order,
- unsigned long count, struct list_head *list,
- int migratetype, int cold)
- {
- int i;
-
- spin_lock(&zone->lock);/* 上层函数已经关了中断,这里需要操作管理区,获取管理区的自旋锁 */
- for (i = 0; i < count; ++i) {/* 重复指定的次数,从伙伴系统中分配页面 */
- /* 从伙伴系统中取出页面 */
- struct page *page = __rmqueue(zone, order, migratetype);
- /* 伙伴系统中没有空闲页了,退出 */
- if (unlikely(page == NULL))
- break;
- /*
- * Split buddy pages returned by expand() are received here
- * in physical page order. The page is added to the callers and
- * list and the list head then moves forward. From the callers
- * perspective, the linked list is ordered by page number in
- * some conditions. This is useful for IO devices that can
- * merge IO requests if the physical pages are ordered
- * properly.
- */
- if (likely(cold == 0))/* 根据调用者的要求,将页面放到每CPU缓存链表的头部或者尾部 */
- list_add(&page->lru, list);
- else
- list_add_tail(&page->lru, list);
- /* 设置页面的迁移类型 */
- set_page_private(page, migratetype);
- list = &page->lru;
- }
- /* 递减管理区的空闲页面计数。 */
- __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
- spin_unlock(&zone->lock);/* 释放管理区的自旋锁 */
- return i;
- }
1.1.1.4 __rmqueue函数
伙伴系统分配页面的总入口是__rmqueue函数:
- /**
- * 从管理区的伙伴系统中取出页面。该函数是分配伙伴页的真正入口。
- * zone: 从该管理区的伙伴系统中分配页面.
- * order: 要分配的页面阶数.即分配的页面数是2^order
- * migratetype: 优先从本参数指定的迁移类型中分配页面.如果失败,再从备用迁移列表中分配.
- */
- static struct page *__rmqueue(struct zone *zone, unsigned int order,
- int migratetype)
- {
- struct page *page;
- retry_reserve:
- /* 优先从指定的迁移类型链表中分配页面 */
- page = __rmqueue_smallest(zone, order, migratetype);
- /**
- * 如果满足以下两个条件,就从备用链表中分配页面:
- * 快速流程没有分配到页面,需要从备用迁移链表中分配.
- * 当前不是从保留的链表中分配.因为保留的链表是最后可用的链表,不能从该链表分配的话,说明本管理区真的没有可用内存了.
- */
- if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
- /* 从备用链表中分配页面. */
- page = __rmqueue_fallback(zone, order, migratetype);
- /*
- * Use MIGRATE_RESERVE rather than fail an allocation. goto
- * is used because __rmqueue_smallest is an inline function
- * and we want just one call site
- */
- if (!page) {/* 备用链表中没有分配到页面,看来得吃老本,从保留链表中分配页面了 */
- migratetype = MIGRATE_RESERVE;
- goto retry_reserve;/* 跳转到retry_reserve,从保留的链表中分配页面 */
- }
- }
- /* 调试代码,很高兴可以飘过 */
- trace_mm_page_alloc_zone_locked(page, order, migratetype);
- return page;
- }
快速流程的处理函数是__rmqueue_smallest:
- /**
- * 遍历指定迁移类型的伙伴系统链表,从链表中移动最小数量的页面返回给调用者.这是伙伴系统的快速处理流程.
- * zone: 在该管理区的伙伴系统中分配页面
- * order: 要分配的页面数量阶.
- * migratetype: 在该迁移类型的链表中获取页面
- */
- static inline
- struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
- int migratetype)
- {
- unsigned int current_order;
- struct free_area * area;
- struct page *page;
- /* Find a page of the appropriate size in the preferred list */
- /* 从指定的阶到最大阶进行遍历,直到找到一个可以分配的链表 */
- for (current_order = order; current_order < MAX_ORDER; ++current_order) {
- /* 找到该阶对应的空闲页面链表 */
- area = &(zone->free_area[current_order]);
- /* 指定迁移类型的空闲链表为空,搜索下一阶的链表 */
- if (list_empty(&area->free_list[migratetype]))
- continue;
- /* 取出链表的第一个元素 */
- page = list_entry(area->free_list[migratetype].next,
- struct page, lru);
- /* 将第一个元素从链表中摘除 */
- list_del(&page->lru);
- /* rmv_page_order将页面的伙伴标志位清0,表示该页不再属于伙伴系统.同时将Private标志清0 */
- rmv_page_order(page);
- /* 当前阶的空闲计数减1 */
- area->nr_free--;
- /**
- * 如果当前阶没有可用的空闲页,而必须将高阶的空闲页面分割,则expand将高阶的页面分割后放回伙伴系统
- * 如:我们将阶为4的页面分割,并向上层返回阶为2的页面,那么,我们需要将其中阶为3,2的页面放回伙伴系统.
- */
- expand(zone, page, order, current_order, area, migratetype);
- return page;
- }
- return NULL;
- }
辅助函数expand:
- /**
- * 将高阶的页面分割成低阶的页面,并放回伙伴系统.
- * low: 分配出去的低阶
- * high: 被分割的高阶
- */
- static inline void expand(struct zone *zone, struct page *page,
- int low, int high, struct free_area *area,
- int migratetype)
- {
- unsigned long size = 1 << high;/* 要被分割的高阶页面数量 */
- /**
- * 我们假设将阶为4的页面组分割,并分配出去阶为2的页
- * 那么我们需要向伙伴系统中分别加入阶为2,3的页面组.
- * 这种情况下,high=4,low=2
- */
- while (high > low) {
- area--;/* area,high,size分别表示本次要放回伙伴系统的链表指针,阶,当前阶的页面数量 */
- high--;
- size >>= 1;
- /* 检查要加入伙伴系统的第一页是否在管理区的范围内 */
- VM_BUG_ON(bad_range(zone, &page[size]));
- /* 将第一页链入相应的迁移类型链表中 */
- list_add(&page[size].lru, &area->free_list[migratetype]);
- /* 该阶的空闲页面计数值加1 */
- area->nr_free++;
- /* 标记页面的阶 */
- set_page_order(&page[size], high);
- }
- }
伙伴系统的慢速处理流程是:
- /**
- * 如果管理区的当前迁移链表中没有可分配的页面时,则从备用迁移链表中分配
- */
- static inline struct page *
- __rmqueue_fallback(struct zone *zone, int order, int start_migratetype)
- {
- struct free_area * area;
- int current_order;
- struct page *page;
- int migratetype, i;
- /* Find the largest possible block of pages in the other list */
- /* 从最高阶搜索,这样可以尽量的将其他迁移列表中的大块分割,避免形成过多的碎片 */
- for (current_order = MAX_ORDER-1; current_order >= order;
- --current_order) {
- for (i = 0; i < MIGRATE_TYPES - 1; i++) {/* 遍历备用的迁移链表 */
- migratetype = fallbacks[start_migratetype][i];
- /* MIGRATE_RESERVE handled later if necessary */
- /* 本函数不处理MIGRATE_RESERVE类型的迁移链表,如果本函数返回NULL,则上层函数直接从MIGRATE_RESERVE中分配 */
- if (migratetype == MIGRATE_RESERVE)
- continue;
- area = &(zone->free_area[current_order]);
- /* 备用链表没有可用的页面,继续搜索下一链表 */
- if (list_empty(&area->free_list[migratetype]))
- continue;
- /* 取备用链表的第一个元素 */
- page = list_entry(area->free_list[migratetype].next,
- struct page, lru);
- /* 备用链表的当前阶计数减1 */
- area->nr_free--;
- /*
- * If breaking a large block of pages, move all free
- * pages to the preferred allocation list. If falling
- * back for a reclaimable kernel allocation, be more
- * aggressive about taking ownership of free pages
- */
- if (unlikely(current_order >= (pageblock_order >> 1)) ||/* 要分割的页面是一个大页面,则将整个页面全部迁移到当前迁移类型的链表中,这样可以避免过多的碎片 */
- start_migratetype == MIGRATE_RECLAIMABLE ||/* 目前分配的是可回收页面,这类页面有突发的特点,将页面全部迁移到可回收链表中,可以避免将其他迁移链表分割成太多的碎片 */
- page_group_by_mobility_disabled) {/* 指定了迁移策略,总是将被分割的页面迁移 */
- unsigned long pages;
- /* 将页面从当前迁移链表转换到start_migratetype指定的迁移链表中 */
- pages = move_freepages_block(zone, page,
- start_migratetype);
- /* Claim the whole block if over half of it is free */
- /* pages是移动的页面数,如果可移动的页面数量较多,则将整个大内存块的迁移类型修改 */
- if (pages >= (1 << (pageblock_order-1)) ||
- page_group_by_mobility_disabled)
- set_pageblock_migratetype(page,
- start_migratetype);
- migratetype = start_migratetype;
- }
- /* Remove the page from the freelists */
- /* 将页面从伙伴伙伴系统链表中移除 */
- list_del(&page->lru);
- rmv_page_order(page);
- /* Take ownership for orders >= pageblock_order */
- if (current_order >= pageblock_order)
- change_pageblock_range(page, current_order,
- start_migratetype);
- /* 将大阶的页面块中未用的部分还回伙伴系统 */
- expand(zone, page, order, current_order, area, migratetype);
- trace_mm_page_alloc_extfrag(page, order, current_order,
- start_migratetype, migratetype);
- return page;
- }
- }
- return NULL;
- }
阅读(774) | 评论(0) | 转发(0) |