您的位置: 首页  >  文章  >  linux内存伙伴算法(初始化内存域和数据结构）

linux内存伙伴算法(初始化内存域和数据结构）

分类: 文章 • 2024-08-26 15:04:40

2019独角兽企业重金招聘Python工程师标准>>> linux内存伙伴算法(初始化内存域和数据结构）

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

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

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

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

linux内存伙伴算法(初始化内存域和数据结构）linux内存伙伴算法(初始化内存域和数据结构）

                                                                                        图1：free_area_init_nodes过程概述

linux内存伙伴算法(初始化内存域和数据结构）

linux内存伙伴算法(初始化内存域和数据结构）

                                          图2：free_area_init_nodes代码流程图

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

[cpp] view plain copy
  1. void __init free_area_init_nodes(unsigned long *max_zone_pfn)  
  2. {  
  3.     unsigned long nid;  
  4.     enum zone_type i;  
  5.   
  6.     /* Sort early_node_map as initialisation assumes it is sorted */  
  7.     sort_node_map();//排序使得后续的任务稍微容易些，排序本身并不特别复杂  
  8.   
  9.     /* Record where the zone boundaries are */  
  10.     memset(arch_zone_lowest_possible_pfn, 0,  
  11.                 sizeof(arch_zone_lowest_possible_pfn));//全局数组arch_zone_lowest_possible_pfn用来存储各个内存域可使用的最低内存页帧编号  
  12.     memset(arch_zone_highest_possible_pfn, 0,  
  13.             sizeof(arch_zone_highest_possible_pfn));//全局数组arch_zone_highest_possible_pfn用来存储各个内存域可使用的最高内存页帧编号  
  14.     arch_zone_lowest_possible_pfn[0] = find_min_pfn_with_active_regions();//辅助函数find_min_pfn_with_active_regions用于找到注册的最低内存域中可用的编号最小的页帧  
  15.   
  16.     arch_zone_highest_possible_pfn[0] = max_zone_pfn[0];//max_zone_pfn记录了各个内存域包含的最大页帧号  
  17.     for (i = 1; i < MAX_NR_ZONES; i++) {//依次遍历，确定各个内存域的边界  
  18.         if (i == ZONE_MOVABLE)//由于ZONE_MOVABLE是一个虚拟内存域，不与真正的硬件内存域关联，该内存域的边界总是设置为0，如后面的代码所示  
  19.             continue;  
  20.         arch_zone_lowest_possible_pfn[i] =  
  21.             arch_zone_highest_possible_pfn[i-1];//第n个内存域的最小页帧，即前一个（第n-1个）内存域的最大页帧  
  22.         arch_zone_highest_possible_pfn[i] =  
  23.             max(max_zone_pfn[i], arch_zone_lowest_possible_pfn[i]);//不出意外，当前内存域的最大页帧由max_zone_pfn给出  
  24.     }  
  25.     arch_zone_lowest_possible_pfn[ZONE_MOVABLE] = 0;  
  26.     arch_zone_highest_possible_pfn[ZONE_MOVABLE] = 0;  
  27.   
  28.     /* Find the PFNs that ZONE_MOVABLE begins at in each node */  
  29.     memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));  
  30.     find_zone_movable_pfns_for_nodes(zone_movable_pfn);//用于计算进入ZONE_MOVABLE的内存数量，详细分析见下文  
  31.   
  32.     /* Print out the zone ranges */  
  33.     printk("Zone PFN ranges:\n");  
  34.     for (i = 0; i < MAX_NR_ZONES; i++) {//将各个内存域的最大、最小页帧号显示出来  
  35.         if (i == ZONE_MOVABLE)  
  36.             continue;  
  37.         printk("  %-8s %8lu -> %8lu\n",  
  38.                 zone_names[i],  
  39.                 arch_zone_lowest_possible_pfn[i],  
  40.                 arch_zone_highest_possible_pfn[i]);  
  41.     }  
  42.   
  43.     /* Print out the PFNs ZONE_MOVABLE begins at in each node */  
  44.     printk("Movable zone start PFN for each node\n");  
  45.     for (i = 0; i < MAX_NUMNODES; i++) {  
  46.         if (zone_movable_pfn[i])//对每个结点来说，zone_movable_pfn[node_id]表示ZONE_MOVABLE在movable_zone内存域中所取得内存的起始地址。内核确保这些页将用于满足符合ZONE_MOVABLE职责的内存分配  
  47.             printk("  Node %d: %lu\n", i, zone_movable_pfn[i]);  
  48.     }  
  49.   
  50.     /* Print out the early_node_map[] */  
  51.     printk("early_node_map[%d] active PFN ranges\n", nr_nodemap_entries);  
  52.     for (i = 0; i < nr_nodemap_entries; i++)//显示各个内存域的分配情况  
  53.         printk("  %3d: %8lu -> %8lu\n", early_node_map[i].nid,  
  54.                         early_node_map[i].start_pfn,  
  55.                         early_node_map[i].end_pfn);  
  56.   
  57.     /* Initialise every node */  
  58.     setup_nr_node_ids();  
  59.     for_each_online_node(nid) {//代码遍历所有的活动结点，并分别对各个结点调用free_area_init_node建立数据结构，该函数需要结点第一个可用的页帧作为一个参数，而find_min_pfn_for_node则从early_node_map数组提取该信息  
  60.         pg_data_t *pgdat = NODE_DATA(nid);  
  61.         free_area_init_node(nid, pgdat, NULL,  
  62.                 find_min_pfn_for_node(nid), NULL);  
  63.   
  64.         /* Any memory on that node */  
  65.         if (pgdat->node_present_pages)// 根据node_present_pages字段判断结点具有内存，则在结点位图中设置N_HIGH_MEMORY标志，该标志只表示结点上存在普通或高端 内存，因此check_for_regular_memory进一步检查低于ZONE_HIGHMEM的内存域中是否有内存，并据此在结点位图中相应地设 置N_NORMAL_MEMORY  
  66.             node_set_state(nid, N_HIGH_MEMORY);  
  67.         check_for_regular_memory(pgdat);  
  68.     }  
  69. }  

free_area_init_node源代码详细分析：

[cpp] view plain copy
  1. void __meminit free_area_init_node(int nid, struct pglist_data *pgdat,  
  2.         unsigned long *zones_size, unsigned long node_start_pfn,  
  3.         unsigned long *zholes_size)  
  4. {  
  5.     pgdat->node_id = nid;  
  6.     pgdat->node_start_pfn = node_start_pfn;  
  7.     calculate_node_totalpages(pgdat, zones_size, zholes_size);//首先累计各个内存域的页数，计算结点中页的总数。对连续内存模型而言，这可以通过zone_sizes_init完成，但calculate_node_totalpages还考虑了内存空洞  
  8.   
  9.     alloc_node_mem_map(pgdat);//分配了该节点的页面描述符数组[pgdat->node_mem_map数组的内存分配]   
  10.   
  11.     free_area_init_core(pgdat, zones_size, zholes_size);//对该节点的每个区[DMA,NORMAL,HIGH]的的结构进行初始化  
  12. }  
calculate_node_totalpages源代码详细分析：
[cpp] view plain copy
  1. static void __meminit calculate_node_totalpages(struct pglist_data *pgdat,  
  2.         unsigned long *zones_size, unsigned long *zholes_size)  
  3. {  
  4.     unsigned long realtotalpages, totalpages = 0;  
  5.     enum zone_type i;  
  6.   
  7.     for (i = 0; i < MAX_NR_ZONES; i++)  
  8.         totalpages += zone_spanned_pages_in_node(pgdat->node_id, i,  
  9.                                 zones_size);//累计计算各个内存域包含空洞的内存总页数  
  10.     pgdat->node_spanned_pages = totalpages;  
  11.   
  12.     realtotalpages = totalpages;  
  13.     for (i = 0; i < MAX_NR_ZONES; i++)  
  14.         realtotalpages -=  
  15.             zone_absent_pages_in_node(pgdat->node_id, i,  
  16.                                 zholes_size)//;以包含空洞的内存总页数累计减去各个内存域中空洞的数量，就可以得出实际可用的内存页数  
  17.     pgdat->node_present_pages = realtotalpages;  
  18.     printk(KERN_DEBUG "On node %d totalpages: %lu\n", pgdat->node_id,  
  19.                             realtotalpages);  
  20. }  
alloc_node_mem_map源代码详细分析：
[cpp] view plain copy
  1. static void __init_refok alloc_node_mem_map(struct pglist_data *pgdat)  
  2. {  
  3.     /* Skip empty nodes */  
  4.     if (!pgdat->node_spanned_pages)//如果内存结点没有没存页，直接返回  
  5.         return;  
  6.   
  7. #ifdef CONFIG_FLAT_NODE_MEM_MAP  
  8.     /* ia64 gets its own node_mem_map, before this, without bootmem */  
  9.     if (!pgdat->node_mem_map) {//如果还没有为结点分配mem_map，则需要为结点分配mem_map  
  10.         unsigned long size, start, end;  
  11.         struct page *map;  
  12.   
  13.         /* 
  14.          * The zone's endpoints aren't required to be MAX_ORDER 
  15.          * aligned but the node_mem_map endpoints must be in order 
  16.          * for the buddy allocator to function correctly. 
  17.          */  
  18.         start = pgdat->node_start_pfn & ~(MAX_ORDER_NR_PAGES - 1);//确定起点，以MAX_ORDER_NR_PAGES的大小对齐  
  19.         end = pgdat->node_start_pfn + pgdat->node_spanned_pages;//计算结束点  
  20.         end = ALIGN(end, MAX_ORDER_NR_PAGES);//以MAX_ORDER_NR_PAGES对齐，与上面的功能一致，将内存映射对齐到伙伴系统的最大分配阶  
  21.         size =  (end - start) * sizeof(struct page);//计算所需内存的大小  
  22.         map = alloc_remap(pgdat->node_id, size);//为内存映射分配内存  
  23.         if (!map)//如果分配不成功，则使用普通的自举内存分配器进行分配  
  24.             map = alloc_bootmem_node(pgdat, size);  
  25.         pgdat->node_mem_map = map + (pgdat->node_start_pfn - start);  
  26.     }  
  27. #ifndef CONFIG_NEED_MULTIPLE_NODES  
  28.     /* 
  29.      * With no DISCONTIG, the global mem_map is just set as node 0's 
  30.      */  
  31.     if (pgdat == NODE_DATA(0)) {  
  32.         mem_map = NODE_DATA(0)->node_mem_map;  
  33. #ifdef CONFIG_ARCH_POPULATES_NODE_MAP  
  34.         if (page_to_pfn(mem_map) != pgdat->node_start_pfn)  
  35.             mem_map -= (pgdat->node_start_pfn - ARCH_PFN_OFFSET);  
  36. #endif /* CONFIG_ARCH_POPULATES_NODE_MAP */  
  37.     }  
  38. #endif  
  39. #endif /* CONFIG_FLAT_NODE_MEM_MAP */  
  40. }  

free_area_init_core源代码详细分析：

[cpp] view plain copy
  1. static void __meminit free_area_init_core(struct pglist_data *pgdat,  
  2.         unsigned long *zones_size, unsigned long *zholes_size)  
  3. {  
  4.     enum zone_type j;  
  5.     int nid = pgdat->node_id;  
  6.     unsigned long zone_start_pfn = pgdat->node_start_pfn;  
  7.     int ret;  
  8.   
  9.     pgdat_resize_init(pgdat);  
  10.     pgdat->nr_zones = 0;  
  11.     init_waitqueue_head(&pgdat->kswapd_wait);  
  12.     pgdat->kswapd_max_order = 0;  
  13.       
  14.     for (j = 0; j < MAX_NR_ZONES; j++) {  
  15.         struct zone *zone = pgdat->node_zones + j;  
  16.         unsigned long size, realsize, memmap_pages;  
  17.   
  18.         size = zone_spanned_pages_in_node(nid, j, zones_size);//内存域跨域的页数  
  19.         realsize = size - zone_absent_pages_in_node(nid, j,  
  20.                                 zholes_size);//内存域的可用长度，可通过跨域的页数减去空洞覆盖的页数而得到  
  21.   
  22.         /* 
  23.          * Adjust realsize so that it accounts for how much memory 
  24.          * is used by this zone for memmap. This affects the watermark 
  25.          * and per-cpu initialisations 
  26.          */  
  27.         memmap_pages = (size * sizeof(struct page)) >> PAGE_SHIFT;//用于内存映射需要的页数  
  28.         if (realsize >= memmap_pages) {如果内存域的可用长度大于用于内存映射需要的页数  
  29.             realsize -= memmap_pages;//则将需要映射的页数分配出去  
  30.             printk(KERN_DEBUG  
  31.                 "  %s zone: %lu pages used for memmap\n",  
  32.                 zone_names[j], memmap_pages);  
  33.         } else//否则，显示警告信息，可用内存不足  
  34.             printk(KERN_WARNING  
  35.                 "  %s zone: %lu pages exceeds realsize %lu\n",  
  36.                 zone_names[j], memmap_pages, realsize);  
  37.   
  38.         /* Account for reserved pages */  
  39.         if (j == 0 && realsize > dma_reserve) {  
  40.             realsize -= dma_reserve;  
  41.             printk(KERN_DEBUG "  %s zone: %lu pages reserved\n",  
  42.                     zone_names[0], dma_reserve);  
  43.         }//除去用于保留的内存页  
  44.   
  45.         if (!is_highmem_idx(j))  
  46.             nr_kernel_pages += realsize;//nr_kernel_pages表示不包含高端内存的系统内存共有的内存页面数，用于统计所有一致映射的页  
  47.         nr_all_pages += realsize;  
  48.   
  49.         zone->spanned_pages = size;//跨域的内存页  
  50.         zone->present_pages = realsize;//经过一系列初始化之后，还可使用的内存页  
  51. #ifdef CONFIG_NUMA  
  52.         zone->node = nid;  
  53.         zone->min_unmapped_pages = (realsize*sysctl_min_unmapped_ratio)/ 100;//这句话不理解，请指教  
  54.         zone->min_slab_pages = (realsize * sysctl_min_slab_ratio) / 100;//这句话不理解，请指教  
  55. #endif  
  56.         zone->name = zone_names[j];  
  57.         spin_lock_init(&zone->lock);//关于锁机制，自己还没有学到，后面会详细介绍锁机制  
  58.         spin_lock_init(&zone->lru_lock);  
  59.         zone_seqlock_init(zone);  
  60.         zone->zone_pgdat = pgdat;  
  61.   
  62.         zone->prev_priority = DEF_PRIORITY;  
  63.   
  64.         zone_pcp_init(zone);//初始化该内存域的per_cpu缓存  
  65.         INIT_LIST_HEAD(&zone->active_list);  
  66.         INIT_LIST_HEAD(&zone->inactive_list);  
  67.         zone->nr_scan_active = 0;  
  68.         zone->nr_scan_inactive = 0;  
  69.         zap_zone_vm_stats(zone);  
  70.         zone->flags = 0;  
  71.         if (!size)  
  72.             continue;  
  73.   
  74.         set_pageblock_order(pageblock_default_order());  
  75.         setup_usemap(pgdat, zone, size);  
  76.         ret = init_currently_empty_zone(zone, zone_start_pfn,  
  77.                         size, MEMMAP_EARLY);//init_currently_empty_zone用于初始化free_area列表，并将属于该内存域的所有page实例都设置为初始默认值  
  78.         BUG_ON(ret);  
  79.         zone_start_pfn += size;  
  80.     }  
  81. }  
check_for_regular_memory源代码详细分析：
[cpp] view plain copy
  1. static void check_for_regular_memory(pg_data_t *pgdat)  
  2. {  
  3. #ifdef CONFIG_HIGHMEM  
  4.     enum zone_type zone_type;  
  5.   
  6.     for (zone_type = 0; zone_type <= ZONE_NORMAL; zone_type++) {//进一步检查低于ZONE_HIGHMEM的内存域中是否有内存  
  7.   
  8.         struct zone *zone = &pgdat->node_zones[zone_type];  
  9.         if (zone->present_pages)  
  10.             node_set_state(zone_to_nid(zone), N_NORMAL_MEMORY);//并根据上面的检查在结点位图中相应地设置N_NORMAL_MEMORY  
  11.   
  12.     }  

  13. #endif 

  14. }

转载于:https://my.oschina.net/u/174242/blog/76833

相关推荐