笔记02-深入理解Linux内核-章8内存管理1

// 32位系统的page->flags位分配（32位）
+-------------------------------------------------+
| 31 - 24    | 23 - 16    | 15 - 8     | 7 - 0    |
+-------------------------------------------------+
| 未使用      | 节点ID      | 管理区ID    | 页状态位  |
+-------------------------------------------------+

// 具体定义：
#define NODES_SHIFT     8   // 但实际可能只用2-3位
#define ZONES_SHIFT     8   // 实际只用2-3位
#define NODES_PGSHIFT   (ZONES_SHIFT + ZONES_PGSHIFT)
#define ZONES_PGSHIFT   (/* 其他标志位占用的位数 */)

// linux version : 6.17.2
/*
 * Describes one page->virtual association
 */
struct page_address_map {
	struct page *page;
	void *virtual;
	struct list_head list;
};

static struct page_address_map page_address_maps[LAST_PKMAP];

/*
 * Hash table bucket
 */
static struct page_address_slot {
	struct list_head lh;			/* List of page_address_maps */
	spinlock_t lock;			/* Protect this bucket's list */
} ____cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];

static struct page_address_slot *page_slot(const struct page *page)
{
	return &page_address_htable[hash_ptr(page, PA_HASH_ORDER)];
}

#define page_to_virt(page)	__va(((((page) - mem_map) << PAGE_SHIFT) + PAGE_OFFSET))

// linux version : 6.17.2
/**
 * kmap_high - map a highmem page into memory
 * @page: &struct page to map
 *
 * Returns the page's virtual memory address.
 *
 * We cannot call this from interrupts, as it may block.
 */
void *kmap_high(struct page *page)
{
	unsigned long vaddr;

	/*
	 * For highmem pages, we can't trust "virtual" until
	 * after we have the lock.
	 */
	lock_kmap();
	vaddr = (unsigned long)page_address(page);
	if (!vaddr)
		vaddr = map_new_virtual(page);
	pkmap_count[PKMAP_NR(vaddr)]++;
	BUG_ON(pkmap_count[PKMAP_NR(vaddr)] < 2);
	unlock_kmap();
	return (void *) vaddr;
}

	count = get_pkmap_entries_count(color);
	/* Find an empty entry */
	for (;;) {
		last_pkmap_nr = get_next_pkmap_nr(color);
		if (no_more_pkmaps(last_pkmap_nr, color)) {
			flush_all_zero_pkmaps();
			count = get_pkmap_entries_count(color);
		}
		if (!pkmap_count[last_pkmap_nr])
			break;	/* Found a usable entry */
		if (--count)
			continue;

		/*
		 * Sleep for somebody else to unmap their entries
		 */
		{
			DECLARE_WAITQUEUE(wait, current);
			wait_queue_head_t *pkmap_map_wait =
				get_pkmap_wait_queue_head(color);

			__set_current_state(TASK_UNINTERRUPTIBLE);
			add_wait_queue(pkmap_map_wait, &wait);
			unlock_kmap();
			schedule();
			remove_wait_queue(pkmap_map_wait, &wait);
			lock_kmap();

			/* Somebody else might have mapped it while we slept */
			if (page_address(page))
				return (unsigned long)page_address(page);

			/* Re-start */
			goto start;
		}

void kunmap_high(struct page *page)
{
	unsigned long vaddr;
	unsigned long nr;
	unsigned long flags;
	int need_wakeup;
	unsigned int color = get_pkmap_color(page);
	wait_queue_head_t *pkmap_map_wait;

	lock_kmap_any(flags);
	vaddr = (unsigned long)page_address(page);
	BUG_ON(!vaddr);
	nr = PKMAP_NR(vaddr);

	/*
	 * A count must never go down to zero
	 * without a TLB flush!
	 */
	need_wakeup = 0;
	switch (--pkmap_count[nr]) {
	case 0:
		BUG();
	case 1:
		/*
		 * Avoid an unnecessary wake_up() function call.
		 * The common case is pkmap_count[] == 1, but
		 * no waiters.
		 * The tasks queued in the wait-queue are guarded
		 * by both the lock in the wait-queue-head and by
		 * the kmap_lock.  As the kmap_lock is held here,
		 * no need for the wait-queue-head's lock.  Simply
		 * test if the queue is empty.
		 */
		pkmap_map_wait = get_pkmap_wait_queue_head(color);
		need_wakeup = waitqueue_active(pkmap_map_wait);
	}
	unlock_kmap_any(flags);

	/* do wake-up, if needed, race-free outside of the spin lock */
	if (need_wakeup)
		wake_up(pkmap_map_wait);
}
EXPORT_SYMBOL(kunmap_high);

/*
* 内存区域（zone）中的伙伴系统结构
**/
struct zone {
    // ...

    /* 伙伴系统核心数据结构 */
    struct free_area free_area[MAX_ORDER];

    // 每CPU页面缓存
    struct per_cpu_pageset __percpu *pageset;

    // 内存水位线
    unsigned long watermark[NR_WMARK];  // WMARK_MIN, WMARK_LOW, WMARK_HIGH

    // 保护锁
    spinlock_t lock;

    // ...
};

/*
* 空闲区域描述符（free_area）
**/
#define MAX_ORDER 11  // 通常为11，最大支持2^10=1024个连续页框

struct free_area {
    struct list_head free_list[MIGRATE_TYPES];  // 按迁移类型分类的空闲链表
    unsigned long nr_free;                      // 该阶数的空闲块总数
};

// 迁移类型定义（防止内存碎片）
enum migratetype {
    MIGRATE_UNMOVABLE,      // 不可移动页（内核核心数据）
    MIGRATE_MOVABLE,        // 可移动页（用户进程内存）
    MIGRATE_RECLAIMABLE,    // 可回收页（文件缓存等）
    MIGRATE_PCPTYPES,       // 每CPU页面类型
    MIGRATE_HIGHATOMIC,     // 高阶原子分配
    MIGRATE_CMA,            // 连续内存分配器
    MIGRATE_ISOLATE,        // 不能从此链表分配
    MIGRATE_TYPES           // 类型总数
};

/*
* 页面描述符中的伙伴系统信息
**/
struct page {
    // 伙伴系统相关字段
    struct list_head lru;           // 用于链接到空闲链表
    unsigned long private;          // 用于存储伙伴系统的阶数(order)

    // 引用计数和标志位
    atomic_t _refcount;
    unsigned long flags;

    // ...
};

/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *__alloc_frozen_pages_noprof(gfp_t gfp, unsigned int order,
		int preferred_nid, nodemask_t *nodemask)
{
	// ...
	if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
			&alloc_gfp, &alloc_flags))
		return NULL;

	/*
	 * Forbid the first pass from falling back to types that fragment
	 * memory until all local zones are considered.
	 */
	alloc_flags |= alloc_flags_nofragment(zonelist_zone(ac.preferred_zoneref), gfp);

	/* First allocation attempt */
	page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
	if (likely(page))
		goto out;

	alloc_gfp = gfp;
	ac.spread_dirty_pages = false;

	/*
	 * Restore the original nodemask if it was potentially replaced with
	 * &cpuset_current_mems_allowed to optimize the fast-path attempt.
	 */
	ac.nodemask = nodemask;

	page = __alloc_pages_slowpath(alloc_gfp, order, &ac);
	// ...
}

static struct page *get_page_from_freelist(gfp_t gfp_mask, unsigned int order,
                      int alloc_flags, const struct alloc_context *ac)
{
    struct zoneref *z;
    struct zone *zone;
    struct page *page = NULL;

    // 遍历所有合适的内存区域
    for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
					ac->nodemask) {
        // 检查水位线
 		if (zone_watermark_fast(zone, order, mark,
					ac->highest_zoneidx, alloc_flags,
					gfp_mask))
		// ...

        // 尝试从伙伴系统分配
 		page = rmqueue(zonelist_zone(ac->preferred_zoneref), zone, order,
				gfp_mask, alloc_flags, ac->migratetype);
		if (page) {
			prep_new_page(page, order, gfp_mask, alloc_flags);

			/*
			 * If this is a high-order atomic allocation then check
			 * if the pageblock should be reserved for the future
			 */
			if (unlikely(alloc_flags & ALLOC_HIGHATOMIC))
				reserve_highatomic_pageblock(page, order, zone);

			return page;
		} else {
			// ...
		}
	}
	// ...

    return NULL;
}

static inline
struct page *rmqueue(struct zone *preferred_zone,
			struct zone *zone, unsigned int order,
			gfp_t gfp_flags, unsigned int alloc_flags,
			int migratetype)
{
	struct page *page;

	// 1. 首先尝试从 PCP 分配
	if (likely(pcp_allowed_order(order))) {
		page = rmqueue_pcplist(preferred_zone, zone, order,
				       migratetype, alloc_flags);
		if (likely(page))
			goto out;  // PCP 分配成功，直接返回
	}

	// 2. PCP 分配失败，回退到伙伴系统
	page = rmqueue_buddy(preferred_zone, zone, order, alloc_flags,
							migratetype);

	// ...
	return page;
}

static __always_inline
struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone,
			   unsigned int order, unsigned int alloc_flags,
			   int migratetype)
{
	// ...
	do {
		if (alloc_flags & ALLOC_HIGHATOMIC)
			page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
		if (!page) {
			enum rmqueue_mode rmqm = RMQUEUE_NORMAL;

			page = __rmqueue(zone, order, migratetype, alloc_flags, &rmqm);

			/*
			 * If the allocation fails, allow OOM handling and
			 * order-0 (atomic) allocs access to HIGHATOMIC
			 * reserves as failing now is worse than failing a
			 * high-order atomic allocation in the future.
			 */
			if (!page && (alloc_flags & (ALLOC_OOM|ALLOC_NON_BLOCK)))
				page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);

			if (!page) {
				spin_unlock_irqrestore(&zone->lock, flags);
				return NULL;
			}
		}
	} while (check_new_pages(page, order));
	// ...
}

static __always_inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
						int migratetype)  // ← 迁移类型参数
{
	unsigned int current_order;
	struct free_area *area;
	struct page *page;

	/* 在指定迁移类型的空闲链表中查找合适大小的页面 */
	for (current_order = order; current_order < NR_PAGE_ORDERS; ++current_order) {
		area = &(zone->free_area[current_order]);
		page = get_page_from_free_area(area, migratetype);  // ← 关键：按迁移类型获取
		if (!page)
			continue;

		page_del_and_expand(zone, page, order, current_order,
				    migratetype);  // ← 迁移类型传递到拆分逻辑
		return page;
	}
	return NULL;
}

// 2.6.11.1
struct per_cpu_pages {
	int count;		/* number of pages in the list */
	int low;		/* low watermark, refill needed */
	int high;		/* high watermark, emptying needed */
	int batch;		/* chunk size for buddy add/remove */
	struct list_head list;	/* the list of pages */
};

struct per_cpu_pageset {
	struct per_cpu_pages pcp[2];	/* 0: hot.  1: cold */
#ifdef CONFIG_NUMA
	unsigned long numa_hit;		/* allocated in intended node */
	unsigned long numa_miss;	/* allocated in non intended node */
	unsigned long numa_foreign;	/* was intended here, hit elsewhere */
	unsigned long interleave_hit; 	/* interleaver prefered this zone */
	unsigned long local_node;	/* allocation from local node */
	unsigned long other_node;	/* allocation from other node */
#endif
} ____cacheline_aligned_in_smp;


// 6.17.2
struct per_cpu_pages {
	spinlock_t lock;	/* Protects lists field */
	int count;		/* number of pages in the list */
	int high;		/* high watermark, emptying needed */
	int high_min;		/* min high watermark */
	int high_max;		/* max high watermark */
	int batch;		/* chunk size for buddy add/remove */
	u8 flags;		/* protected by pcp->lock */
	u8 alloc_factor;	/* batch scaling factor during allocate */
#ifdef CONFIG_NUMA
	u8 expire;		/* When 0, remote pagesets are drained */
#endif
	short free_count;	/* consecutive free count */

	/* Lists of pages, one per migrate type stored on the pcp-lists */
	struct list_head lists[NR_PCP_LISTS];
} ____cacheline_aligned_in_smp;

/* Remove page from the per-cpu list, caller must protect the list */
static inline
struct page *__rmqueue_pcplist(struct zone *zone, unsigned int order,
			int migratetype,
			unsigned int alloc_flags,
			struct per_cpu_pages *pcp,
			struct list_head *list)
{
	struct page *page;

	do {
		if (list_empty(list)) {
			int batch = nr_pcp_alloc(pcp, zone, order);
			int alloced;

			alloced = rmqueue_bulk(zone, order,
					batch, list,
					migratetype, alloc_flags);

			pcp->count += alloced << order;
			if (unlikely(list_empty(list)))
				return NULL;
		}

		page = list_first_entry(list, struct page, pcp_list);
		list_del(&page->pcp_list);
		pcp->count -= 1 << order;
	} while (check_new_pages(page, order));

	return page;
}

/*
 * Free a pcp page
 */
static void __free_frozen_pages(struct page *page, unsigned int order,
				fpi_t fpi_flags)
{
	// ......
	pcp_trylock_prepare(UP_flags);
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
	if (pcp) {
		free_frozen_page_commit(zone, pcp, page, migratetype, order, fpi_flags);
		pcp_spin_unlock(pcp);
	} else {
		free_one_page(zone, page, pfn, order, fpi_flags);
	}
	pcp_trylock_finish(UP_flags);
}

static void free_frozen_page_commit(struct zone *zone,
		struct per_cpu_pages *pcp, struct page *page, int migratetype,
		unsigned int order, fpi_t fpi_flags)
{
	int high, batch;
	int pindex;
	bool free_high = false;

	/*
	 * On freeing, reduce the number of pages that are batch allocated.
	 * See nr_pcp_alloc() where alloc_factor is increased for subsequent
	 * allocations.
	 */
	pcp->alloc_factor >>= 1;
	__count_vm_events(PGFREE, 1 << order);
	pindex = order_to_pindex(migratetype, order);
	list_add(&page->pcp_list, &pcp->lists[pindex]);
	pcp->count += 1 << order;

	batch = READ_ONCE(pcp->batch);
	/*
	 * As high-order pages other than THP's stored on PCP can contribute
	 * to fragmentation, limit the number stored when PCP is heavily
	 * freeing without allocation. The remainder after bulk freeing
	 * stops will be drained from vmstat refresh context.
	 */
	if (order && order <= PAGE_ALLOC_COSTLY_ORDER) {
		free_high = (pcp->free_count >= (batch + pcp->high_min / 2) &&
			     (pcp->flags & PCPF_PREV_FREE_HIGH_ORDER) &&
			     (!(pcp->flags & PCPF_FREE_HIGH_BATCH) ||
			      pcp->count >= batch));
		pcp->flags |= PCPF_PREV_FREE_HIGH_ORDER;
	} else if (pcp->flags & PCPF_PREV_FREE_HIGH_ORDER) {
		pcp->flags &= ~PCPF_PREV_FREE_HIGH_ORDER;
	}
	if (pcp->free_count < (batch << CONFIG_PCP_BATCH_SCALE_MAX))
		pcp->free_count += (1 << order);

	if (unlikely(fpi_flags & FPI_TRYLOCK)) {
		/*
		 * Do not attempt to take a zone lock. Let pcp->count get
		 * over high mark temporarily.
		 */
		return;
	}
	high = nr_pcp_high(pcp, zone, batch, free_high);
	if (pcp->count >= high) {
		free_pcppages_bulk(zone, nr_pcp_free(pcp, batch, high, free_high),
				   pcp, pindex);
		if (test_bit(ZONE_BELOW_HIGH, &zone->flags) &&
		    zone_watermark_ok(zone, 0, high_wmark_pages(zone),
				      ZONE_MOVABLE, 0))
			clear_bit(ZONE_BELOW_HIGH, &zone->flags);
	}
}

开始分配请求
    ├─ 第一步：选择起点
    │    根据GFP标志确定从哪个管理区开始
    │
    ├─ 第二步：检查水位
    │    ├─ 水位充足(>low) → 尝试分配
    │    ├─ 水位警戒(min~low) → 唤醒kswapd，然后尝试
    │    └─ 水位危险(<min) → 直接回收，然后尝试
    │
    ├─ 第三步：分配尝试
    │    ├─ 成功 → 返回内存 ✅
    │    └─ 失败 → fallback到下一个管理区
    │
    ├─ 第四步：fallback循环
    │    按优先级尝试所有允许的管理区
    │
    └─ 第五步：最终手段
         如果所有管理区都失败：
         1. 内存压缩
         2. 直接回收
         3. OOM Killer

开始释放
    ├─ 检查释放条件
    │    引用计数减到0？页是否有效？
    │
    ├─ 单页释放(order=0)
    │    ├─ 放入当前CPU的热缓存
    │    ├─ 如果缓存超过高水位线
    │    │     批量释放到伙伴系统
    │    │         ↓
    │    │     尝试伙伴合并
    │    │     更新空闲链表
    │    │
    │    └─ 只更新Per-CPU计数，快速返回
    │
    └─ 多页释放(order>0)
          ├─ 直接调用伙伴系统
          ├─ 循环尝试伙伴合并
          │    检查相邻块是否空闲且同类型
          │    如果可以合并，形成更大块
          │    继续尝试更高阶合并
          │
          ├─ 将最终块加入空闲链表
          ├─ 更新管理区空闲页计数
          └─ 可能唤醒等待内存的进程