linuxメモリ管理--パートナーシステムとメモリ分配器
15177 ワード
3.1ページ枠の管理は、すべてのページ枠記述子をmem_に保存します.map配列にあります
3.1.1 pageデータ構造
3.2パートナーシステムは通常alloc_を使用します.pages()、alloc_page(),__ゲットするfree_pages()、__ゲットするfree_page()、get_ゼロドドドドページ枠を取得するために、最初の2つはページ記述子のアドレスであり、後の2つは物理ページの線形アドレスである.ハイエンドメモリの割り当ては前の2つの分配関数だけで、後の2つは線形アドレスなので、直接使用できません.これらの4つの関数インターフェースは最終的には、パートナーシステムの関連インターフェースにメモリの割り当てを呼び出す.
Linuxカーネルのパートナーアルゴリズムはメモリのかけらを最大限に減らしました.実は自分の最大の努力を尽くしてメモリのかけらを減らしました.その考えは、物理メモリを11ブロックのチェーンテーブルに分割し、各チェーンテーブルはサイズが1,2,4,8...512,1024の連続ページブロックを含む.例えば、256個の連続ページ枠を割り当てるなら、まずブロックサイズ256のチェーンテーブルに空きブロックを検索し、直接に戻ることがあれば、512の大きさのチェーンテーブルに行って検索し、512の大きさのブロックを2つの部分に分けて返します.部分は256サイズのチェーンテーブルに挿入します.512サイズのチェーンテーブルにまだない場合、1024サイズのチェーンテーブルに検索します.256サイズのブロックを取り出して、残りの512,256のブロックをそれぞれのチェーンに挿入します.メモリのリリースのプロセスは逆です.割り当て中に大きな塊で分解された小さい塊の中で分配されていないブロックが放出されるのを待ち続けています.統合の操作はページリリースの過程において、最終的な結果は大きな塊を分解していないのに相当します.パートナーシステムはずっとこの結果に収束しています.パートナーシステムは二つの方向に分解と結合を行います.もし最初のシステムに破片がないなら、最終的なかけらは最小化されます.相互逆の操作は最大の力でかけらの生成を相殺するからです.これは本質です.パートナーシステムのアルゴリズムは主にzone記述子の中のzone_を使用している.mem_mapフィールドとfree_アレア配列mem_mapはメモリ管理エリアの物理ページの先頭アドレスを指しています.free_araは上に述べた11のチェーンを表しています.struct free_area{struct listuheadfreemulist]//ブロックチェーンのヘッダunsigned long*map;/ブロック割り当てのビットマップ}.struct free_araの中のfree_listフィールドはアイドルメモリブロックのチェーンヘッダであり、空きメモリブロックはメモリディスクリプタのlllフィールドを通じてリンクテーブルとなり、1つのサイズは1024ページのフレームのメモリブロックであり、その最初のページボックスのprvateフィールドは対応するorderすなわち10を保存しています.最初のページボックスにもタグビットがあり、buddyのメモリブロックであるかどうかを示しています.ページボックスが解放された時に、このフィールドでそのパートナーメモリブロックとより大きなメモリブロックに統合できるかどうかを判定します.
3.2.1メモリブロックの割り当て
3.1.1 pageデータ構造
struct page {
page_flags_t flags; //
atomic_t _count;// , -1
atomic_t _mapcount;// ，
unsigned long private;// ， ，
struct address_space *mapping;// address _space , ， anon_vma ，anon_vma vm_area_struct.
pgoff_t index; //
struct list_head lru; //
};
struct zone {
unsigned long free_pages;//
unsigned long pages_min, pages_low, pages_high;
//pages_min ，pages_low，pages_high
//
struct per_cpu_pageset pageset[NR_CPUS];//pageset cpu ，
spinlock_t lock; //
struct free_area free_area[MAX_ORDER];// ，
spinlock_t lru_lock; // lru
struct list_head active_list;// active
struct list_head inactive_list;// inactive
unsigned long nr_scan_active;// ，
unsigned long nr_scan_inactive;//
unsigned long nr_active;//
unsigned long nr_inactive;//
unsigned long pages_scanned;//
int all_unreclaimable;// ，
int temp_priority; //
int prev_priority; //
wait_queue_head_t * wait_table;// ，
unsigned long wait_table_size;//
unsigned long wait_table_bits;//
struct pglist_data *zone_pgdat;//
struct page *zone_mem_map;//
unsigned long zone_start_pfn;//
unsigned long spanned_pages;//
unsigned long present_pages;// ，
char *name;//
} ____cacheline_maxaligned_in_smp;
typedef struct pglist_data {
struct zone node_zones[MAX_NR_ZONES];//
struct zonelist node_zonelists[GFP_ZONETYPES];//zonelist ，
int nr_zones;//
struct page *node_mem_map;//
struct bootmem_data *bdata;
unsigned long node_start_pfn;//
unsigned long node_present_pages; // ，
unsigned long node_spanned_pages; // ，
int node_id;// id
struct pglist_data *pgdat_next;//
wait_queue_head_t kswapd_wait;//kswapd ， kswapd
struct task_struct *kswapd; // kswapd ， alloc_page ，
} pg_data_t;
3.2パートナーシステムは通常alloc_を使用します.pages()、alloc_page(),__ゲットするfree_pages()、__ゲットするfree_page()、get_ゼロドドドドページ枠を取得するために、最初の2つはページ記述子のアドレスであり、後の2つは物理ページの線形アドレスである.ハイエンドメモリの割り当ては前の2つの分配関数だけで、後の2つは線形アドレスなので、直接使用できません.これらの4つの関数インターフェースは最終的には、パートナーシステムの関連インターフェースにメモリの割り当てを呼び出す.
Linuxカーネルのパートナーアルゴリズムはメモリのかけらを最大限に減らしました.実は自分の最大の努力を尽くしてメモリのかけらを減らしました.その考えは、物理メモリを11ブロックのチェーンテーブルに分割し、各チェーンテーブルはサイズが1,2,4,8...512,1024の連続ページブロックを含む.例えば、256個の連続ページ枠を割り当てるなら、まずブロックサイズ256のチェーンテーブルに空きブロックを検索し、直接に戻ることがあれば、512の大きさのチェーンテーブルに行って検索し、512の大きさのブロックを2つの部分に分けて返します.部分は256サイズのチェーンテーブルに挿入します.512サイズのチェーンテーブルにまだない場合、1024サイズのチェーンテーブルに検索します.256サイズのブロックを取り出して、残りの512,256のブロックをそれぞれのチェーンに挿入します.メモリのリリースのプロセスは逆です.割り当て中に大きな塊で分解された小さい塊の中で分配されていないブロックが放出されるのを待ち続けています.統合の操作はページリリースの過程において、最終的な結果は大きな塊を分解していないのに相当します.パートナーシステムはずっとこの結果に収束しています.パートナーシステムは二つの方向に分解と結合を行います.もし最初のシステムに破片がないなら、最終的なかけらは最小化されます.相互逆の操作は最大の力でかけらの生成を相殺するからです.これは本質です.パートナーシステムのアルゴリズムは主にzone記述子の中のzone_を使用している.mem_mapフィールドとfree_アレア配列mem_mapはメモリ管理エリアの物理ページの先頭アドレスを指しています.free_araは上に述べた11のチェーンを表しています.struct free_area{struct listuheadfreemulist]//ブロックチェーンのヘッダunsigned long*map;/ブロック割り当てのビットマップ}.struct free_araの中のfree_listフィールドはアイドルメモリブロックのチェーンヘッダであり、空きメモリブロックはメモリディスクリプタのlllフィールドを通じてリンクテーブルとなり、1つのサイズは1024ページのフレームのメモリブロックであり、その最初のページボックスのprvateフィールドは対応するorderすなわち10を保存しています.最初のページボックスにもタグビットがあり、buddyのメモリブロックであるかどうかを示しています.ページボックスが解放された時に、このフィールドでそのパートナーメモリブロックとより大きなメモリブロックに統合できるかどうかを判定します.
3.2.1メモリブロックの割り当て
static struct page *__rmqueue(struct zone *zone, unsigned int order)
{
struct free_area * area;
unsigned int current_order;
struct page *page;
// order
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
// current_order
area = zone->free_area + current_order;
// ，
if (list_empty(&area->free_list))
continue;
// page lru
page = list_entry(area->free_list.next, struct page, lru);
list_del(&page->lru);
// page buddy ， private 0
rmv_page_order(page);
area->nr_free--;
zone->free_pages -= 1UL << order;
// current_order order ，
//
expand(zone, page, order, current_order, area);
return page;
}
return NULL;
}
static inline void __free_one_page(struct page *page,
struct zone *zone, unsigned int order)
{
unsigned long page_idx;
int order_size = 1 << order;
if (unlikely(PageCompound(page)))
destroy_compound_page(page, order);
page_idx = page_to_pfn(page) & ((1 << MAX_ORDER) - 1);
//
zone->free_pages += order_size;
while (order < MAX_ORDER-1) {
unsigned long combined_idx;
struct free_area *area;
struct page *buddy;
//
buddy = page + (page_idx^(1<<order) -page_idx);
//
if (!page_is_buddy(page, 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);
// page index
combined_idx = __find_combined_index(page_idx, order);
// page
page = page + (combined_idx - page_idx);
page_idx = combined_idx;
order++;
}
// page->private ，
set_page_order(page, order);
//
list_add(&page->lru, &zone->free_area[order].free_list);
zone->free_area[order].nr_free++;
}
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);
int cpu;
again:
// cpu
cpu = get_cpu();
// ，
if (likely(order == 0)) {
struct per_cpu_pages *pcp;
pcp = &zone_pcp(zone, cpu)->pcp[cold];
local_irq_save(flags);
// ，
if (!pcp->count) {
// ，
// 1 ， batch
pcp->count += rmqueue_bulk(zone, 0,
pcp->batch, &pcp->list);
if (unlikely(!pcp->count))
goto failed;
}
// page
page = list_entry(pcp->list.next, struct page, lru);
list_del(&page->lru);
pcp->count--;
} else {
// ， __rmqueue()
spin_lock_irqsave(&zone->lock, flags);
page = __rmqueue(zone, order);
spin_unlock(&zone->lock);
if (!page)
goto failed;
}
local_irq_restore(flags);
put_cpu();
:
return page;
failed:
local_irq_restore(flags);
put_cpu();
return NULL;
}
free_hot_cold_page()：
static void fastcall free_hot_cold_page(struct page *page, int cold)
{
// page->flag zone
struct zone *zone = page_zone(page);
struct per_cpu_pages *pcp;
unsigned long flags;
kernel_map_pages(page, 1, 0);
//
pcp = &zone_pcp(zone, get_cpu())->pcp[cold];
local_irq_save(flags);
__count_vm_event(PGFREE);
//
list_add(&page->lru, &pcp->list);
pcp->count++;
// pcp->high， batch
//
if (pcp->count >= pcp->high) {
free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
pcp->count -= pcp->batch;
}
local_irq_restore(flags);
put_cpu();
}
struct page * fastcall
__alloc_pages(gfp_t gfp_mask, unsigned int order,
struct zonelist *zonelist)
{
const gfp_t wait = gfp_mask & __GFP_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);
restart:
//zonelist->zones
z = zonelist->zones;
// zone->page_low
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
zonelist, ALLOC_WMARK_LOW|ALLOC_CPUSET);
// ，
if (page)
goto got_pg;
// ， kswapd
do {
wakeup_kswapd(*z, order);
} while (*(++z));
// kswapd ， ， zone->min_pages，
alloc_flags = ALLOC_WMARK_MIN;
// ，
// ， ALLOC_HARDER
if ((unlikely(rt_task(p)) && !in_interrupt()) || !wait)
alloc_flags |= ALLOC_HARDER;
//__GFP_HIGH
if (gfp_mask & __GFP_HIGH)
alloc_flags |= ALLOC_HIGH;
// GFP_ATOMIC
if (wait)
alloc_flags |= ALLOC_CPUSET;
//
page = get_page_from_freelist(gfp_mask, order, zonelist, alloc_flags);
// ，OK，
if (page)
goto got_pg;
// ， ， ，
//PF_MEMALLOC ，
if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE)))
&& !in_interrupt()) {
//__GFP_NOMEMALLOC ， ， ，
//
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;
}
// ， ， NULL
if (!wait)
goto nopage;
rebalance:
//
cond_resched();
/* We now go into synchronous reclaim */
cpuset_memory_pressure_bump();
// PF_MEMALLOC
p->flags |= PF_MEMALLOC;
reclaim_state.reclaimed_slab = 0;
p->reclaim_state = &reclaim_state;
//
did_some_progress = try_to_free_pages(zonelist->zones, gfp_mask);
p->reclaim_state = NULL;
p->flags &= ~PF_MEMALLOC;
// ，
cond_resched();
//
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)) {
// ，
// !!! ， !
page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, order,
zonelist, ALLOC_WMARK_HIGH|ALLOC_CPUSET);
if (page)
goto got_pg;
out_of_memory(zonelist, gfp_mask, order);
goto restart;
}
do_retry = 0;
//gfp_mask GFP_NORETRY
if (!(gfp_mask & __GFP_NORETRY)) {
//GFP_REPEAT,GFP_NOFAIL
if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
do_retry = 1;
if (gfp_mask & __GFP_NOFAIL)
do_retry = 1;
}
// ， blk_congestion_wait() ，
if (do_retry) {
blk_congestion_wait(WRITE, HZ/50);
goto rebalance;
}
nopage:
if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
dump_stack();
show_mem();
}
got_pg:
return page;
}
3.3.2get_page_from_freelist
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 = zonelist->zones;
struct page *page = NULL;
int classzone_idx = zone_idx(*z);
do {
if ((alloc_flags & ALLOC_CPUSET) &&
!cpuset_zone_allowed(*z, gfp_mask))
continue;
if (!(alloc_flags & ALLOC_NO_WATERMARKS)) {
unsigned long mark;
//alloc_flags mark ，mark
// zone_watermark_ok
if (alloc_flags & ALLOC_WMARK_MIN)
mark = (*z)->pages_min;
else if (alloc_flags & ALLOC_WMARK_LOW)
mark = (*z)->pages_low;
else
mark = (*z)->pages_high;
//zone ，
if (!zone_watermark_ok(*z, order, mark,
classzone_idx, alloc_flags))
if (!zone_reclaim_mode ||
!zone_reclaim(*z, gfp_mask, order))
continue;
}
// bufferd_rmqueue
page = buffered_rmqueue(zonelist, *z, order, gfp_mask);
if (page) {
break;
}
} while (*(++z) != NULL);
return page;
}
3.3.3 zone_watermark_ok
int zone_watermark_ok(struct zone *z, int order, unsigned long mark,
int classzone_idx, int alloc_flags)
{
// mark， zone->low,high,min
long min = mark, free_pages = z->free_pages - (1 << order) + 1;
int o;
// __GFP_WAIT ， ALLOC_HIGH ， 1/2
if (alloc_flags & ALLOC_HIGH)
min -= min / 2;
// __GFP_WAIT ， ，
// ， alloc_flag ALLOC_HARDER ,min 1/4
if (alloc_flags & ALLOC_HARDER)
min -= min / 4;
// min
if (free_pages <= min + z->lowmem_reserve[classzone_idx])
return 0;
// 0-order ， ，
// order k min/2(k)
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;
/* Require fewer higher order pages to be free */
min >>= 1;
if (free_pages <= min)
return 0;
}
return 1;
}