ULK 内存管理

 1/*
 2 * Each physical page in the system has a struct page associated with
 3 * it to keep track of whatever it is we are using the page for at the
 4 * moment. Note that we have no way to track which tasks are using
 5 * a page.
 6 */
 7struct page {
 8	page_flags_t flags;		/* Atomic flags, some possibly
 9					 * updated asynchronously */
10	atomic_t _count;		/* Usage count, see below. */
11	atomic_t _mapcount;		/* Count of ptes mapped in mms,
12					 * to show when page is mapped
13					 * & limit reverse map searches.
14					 */
15	unsigned long private;		/* Mapping-private opaque data:
16					 * usually used for buffer_heads
17					 * if PagePrivate set; used for
18					 * swp_entry_t if PageSwapCache
19					 * When page is free, this indicates
20					 * order in the buddy system.
21					 */
22	struct address_space *mapping;	/* If low bit clear, points to
23					 * inode address_space, or NULL.
24					 * If page mapped as anonymous
25					 * memory, low bit is set, and
26					 * it points to anon_vma object:
27					 * see PAGE_MAPPING_ANON below.
28					 */
29	pgoff_t index;			/* Our offset within mapping. */
30	struct list_head lru;		/* Pageout list, eg. active_list
31					 * protected by zone->lru_lock !
32					 */
33	/*
34	 * On machines where all RAM is mapped into kernel address space,
35	 * we can simply calculate the virtual address. On machines with
36	 * highmem some memory is mapped into kernel virtual memory
37	 * dynamically, so we need a place to store that address.
38	 * Note that this field could be 16 bits on x86 ... ;)
39	 *
40	 * Architectures with slow multiplication can define
41	 * WANT_PAGE_VIRTUAL in asm/page.h
42	 */
43#if defined(WANT_PAGE_VIRTUAL)
44	void *virtual;			/* Kernel virtual address (NULL if
45					   not kmapped, ie. highmem) */
46#endif /* WANT_PAGE_VIRTUAL */
47};

 1/*
 2 * The pg_data_t structure is used in machines with CONFIG_DISCONTIGMEM
 3 * (mostly NUMA machines?) to denote a higher-level memory zone than the
 4 * zone denotes.
 5 *
 6 * On NUMA machines, each NUMA node would have a pg_data_t to describe
 7 * it's memory layout.
 8 *
 9 * Memory statistics and page replacement data structures are maintained on a
10 * per-zone basis.
11 */
12struct bootmem_data;
13typedef struct pglist_data {
14	struct zone node_zones[MAX_NR_ZONES];
15	struct zonelist node_zonelists[GFP_ZONETYPES];
16	int nr_zones;
17	struct page *node_mem_map;
18	struct bootmem_data *bdata;
19	unsigned long node_start_pfn;
20	unsigned long node_present_pages; /* total number of physical pages */
21	unsigned long node_spanned_pages; /* total size of physical page
22					     range, including holes */
23	int node_id;
24	struct pglist_data *pgdat_next;
25	wait_queue_head_t kswapd_wait;
26	struct task_struct *kswapd;
27	int kswapd_max_order;
28} pg_data_t;

 1#define MAX_NR_ZONES		3	/* Sync this with ZONES_SHIFT */
 2#define ZONES_SHIFT		2	/* ceil(log2(MAX_NR_ZONES)) */
 3
 4#define NODEZONE_SHIFT (sizeof(page_flags_t)*8 - MAX_NODES_SHIFT - MAX_ZONES_SHIFT)
 5
 6struct zone;
 7extern struct zone *zone_table[];
 8
 9static inline struct zone *page_zone(struct page *page)
10{
11	return zone_table[page->flags >> NODEZONE_SHIFT];
12}

 1/*
 2 * setup_per_zone_lowmem_reserve - called whenever
 3 *	sysctl_lower_zone_reserve_ratio changes.  Ensures that each zone
 4 *	has a correct pages reserved value, so an adequate number of
 5 *	pages are left in the zone after a successful __alloc_pages().
 6 */
 7static void setup_per_zone_lowmem_reserve(void)
 8{
 9	struct pglist_data *pgdat;
10	int j, idx;
11
12	for_each_pgdat(pgdat) {
13		for (j = 0; j < MAX_NR_ZONES; j++) {
14			struct zone * zone = pgdat->node_zones + j;
15			unsigned long present_pages = zone->present_pages;
16
17			zone->lowmem_reserve[j] = 0;
18
19			for (idx = j-1; idx >= 0; idx--) {
20				struct zone * lower_zone = pgdat->node_zones + idx;
21
22				lower_zone->lowmem_reserve[j] = present_pages / sysctl_lowmem_reserve_ratio[idx];
23				present_pages += lower_zone->present_pages;
24			}
25		}
26	}
27}
28
29/*
30 * setup_per_zone_pages_min - called when min_free_kbytes changes.  Ensures 
31 *	that the pages_{min,low,high} values for each zone are set correctly 
32 *	with respect to min_free_kbytes.
33 */
34static void setup_per_zone_pages_min(void)
35{
36	unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);
37	unsigned long lowmem_pages = 0;
38	struct zone *zone;
39	unsigned long flags;
40
41	/* Calculate total number of !ZONE_HIGHMEM pages */
42	for_each_zone(zone) {
43		if (!is_highmem(zone))
44			lowmem_pages += zone->present_pages;
45	}
46
47	for_each_zone(zone) {
48		spin_lock_irqsave(&zone->lru_lock, flags);
49		if (is_highmem(zone)) {
50			/*
51			 * Often, highmem doesn't need to reserve any pages.
52			 * But the pages_min/low/high values are also used for
53			 * batching up page reclaim activity so we need a
54			 * decent value here.
55			 */
56			int min_pages;
57
58			min_pages = zone->present_pages / 1024;
59			if (min_pages < SWAP_CLUSTER_MAX)
60				min_pages = SWAP_CLUSTER_MAX;
61			if (min_pages > 128)
62				min_pages = 128;
63			zone->pages_min = min_pages;
64		} else {
65			/* if it's a lowmem zone, reserve a number of pages 
66			 * proportionate to the zone's size.
67			 */
68			zone->pages_min = (pages_min * zone->present_pages) / 
69			                   lowmem_pages;
70		}
71
72		/*
73		 * When interpreting these watermarks, just keep in mind that:
74		 * zone->pages_min == (zone->pages_min * 4) / 4;
75		 */
76		zone->pages_low   = (zone->pages_min * 5) / 4;
77		zone->pages_high  = (zone->pages_min * 6) / 4;
78		spin_unlock_irqrestore(&zone->lru_lock, flags);
79	}
80}
81
82static int __init init_per_zone_pages_min(void)
83{
84	unsigned long lowmem_kbytes;
85
86	lowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);
87
88	min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
89	if (min_free_kbytes < 128)
90		min_free_kbytes = 128;
91	if (min_free_kbytes > 65536)
92		min_free_kbytes = 65536;
93	setup_per_zone_pages_min();
94	setup_per_zone_lowmem_reserve();
95	return 0;
96}

 1/*
 2 * UMA模型
 3 */
 4#define alloc_pages(gfp_mask, order) \
 5		alloc_pages_node(numa_node_id(), gfp_mask, order)
 6
 7#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)
 8
 9/*
10 * Common helper functions.
11 */
12fastcall unsigned long __get_free_pages(unsigned int gfp_mask, unsigned int order)
13{
14	struct page * page;
15	page = alloc_pages(gfp_mask, order);
16	if (!page)
17		return 0;
18	return (unsigned long) page_address(page);
19}
20
21#define __get_free_page(gfp_mask) \
22		__get_free_pages((gfp_mask),0)
23
24#define __get_dma_pages(gfp_mask, order) \
25		__get_free_pages((gfp_mask) | GFP_DMA,(order))
26
27fastcall unsigned long get_zeroed_page(unsigned int gfp_mask)
28{
29	struct page * page;
30
31	/*
32	 * get_zeroed_page() returns a 32-bit address, which cannot represent
33	 * a highmem page
34	 */
35	BUG_ON(gfp_mask & __GFP_HIGHMEM);
36
37	page = alloc_pages(gfp_mask | __GFP_ZERO, 0);
38	if (page)
39		return (unsigned long) page_address(page);
40	return 0;
41}

 1/* if you forget to add the bitmask here kernel will crash, period */
 2#define GFP_LEVEL_MASK (__GFP_WAIT|__GFP_HIGH|__GFP_IO|__GFP_FS| \
 3			__GFP_COLD|__GFP_NOWARN|__GFP_REPEAT| \
 4			__GFP_NOFAIL|__GFP_NORETRY|__GFP_NO_GROW|__GFP_COMP)
 5
 6#define GFP_ATOMIC	(__GFP_HIGH)
 7#define GFP_NOIO	(__GFP_WAIT)
 8#define GFP_NOFS	(__GFP_WAIT | __GFP_IO)
 9#define GFP_KERNEL	(__GFP_WAIT | __GFP_IO | __GFP_FS)
10#define GFP_USER	(__GFP_WAIT | __GFP_IO | __GFP_FS)
11#define GFP_HIGHUSER	(__GFP_WAIT | __GFP_IO | __GFP_FS | __GFP_HIGHMEM)

 1fastcall void __free_pages(struct page *page, unsigned int order)
 2{
 3	if (!PageReserved(page) && put_page_testzero(page)) {
 4		if (order == 0)
 5			free_hot_page(page);
 6		else
 7			__free_pages_ok(page, order);
 8	}
 9}
10
11fastcall void free_pages(unsigned long addr, unsigned int order)
12{
13	if (addr != 0) {
14		BUG_ON(!virt_addr_valid((void *)addr));
15		__free_pages(virt_to_page((void *)addr), order);
16	}
17}
18
19#define __free_page(page) __free_pages((page), 0)
20#define free_page(addr) free_pages((addr),0)

 1/*
 2 * Ordering is:
 3 *
 4 * FIXADDR_TOP
 5 * 			fixed_addresses
 6 * FIXADDR_START
 7 * 			temp fixed addresses
 8 * FIXADDR_BOOT_START
 9 * 			Persistent kmap area
10 * PKMAP_BASE
11 * VMALLOC_END
12 * 			Vmalloc area
13 * VMALLOC_START
14 * high_memory
15 */
16#define PKMAP_BASE ( (FIXADDR_BOOT_START - PAGE_SIZE*(LAST_PKMAP + 1)) & PMD_MASK )

1/*
2* Virtual_count is not a pure "count".
3*  0 means that it is not mapped, and has not been mapped
4*    since a TLB flush - it is usable.
5*  1 means that there are no users, but it has been mapped
6*    since the last TLB flush - so we can't use it.
7*  n means that there are (n-1) current users of it.
8*/
9static int pkmap_count[LAST_PKMAP];

1/*
2 * Describes one page->virtual association
3 */
4struct page_address_map {
5	struct page *page;
6	void *virtual;
7	struct list_head list;
8};

 1static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
 2{
 3	return hash_long((unsigned long)ptr, bits);
 4}
 5
 6
 7/*
 8 * Hash table bucket
 9 */
10static struct page_address_slot {
11	struct list_head lh;			/* List of page_address_maps */
12	spinlock_t lock;			/* Protect this bucket's list */
13} ____cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];
14
15static struct page_address_slot *page_slot(struct page *page)
16{
17	return &page_address_htable[hash_ptr(page, PA_HASH_ORDER)];
18}
19
20void *page_address(struct page *page)
21{
22	unsigned long flags;
23	void *ret;
24	struct page_address_slot *pas;
25
26	if (!PageHighMem(page))
27		return lowmem_page_address(page);
28
29	pas = page_slot(page);
30	ret = NULL;
31	spin_lock_irqsave(&pas->lock, flags);
32	if (!list_empty(&pas->lh)) {
33		struct page_address_map *pam;
34
35		list_for_each_entry(pam, &pas->lh, list) {
36			if (pam->page == page) {
37				ret = pam->virtual;
38				goto done;
39			}
40		}
41	}
42done:
43	spin_unlock_irqrestore(&pas->lock, flags);
44	return ret;
45}

1void *kmap(struct page *page)
2{
3	might_sleep();
4	if (!PageHighMem(page))
5		return page_address(page);
6	return kmap_high(page);
7}

 1void fastcall *kmap_high(struct page *page)
 2{
 3	unsigned long vaddr;
 4
 5	/*
 6	 * For highmem pages, we can't trust "virtual" until
 7	 * after we have the lock.
 8	 *
 9	 * We cannot call this from interrupts, as it may block
10	 */
11	spin_lock(&kmap_lock);
12	vaddr = (unsigned long)page_address(page);
13	if (!vaddr)
14		vaddr = map_new_virtual(page);
15	pkmap_count[PKMAP_NR(vaddr)]++;
16	if (pkmap_count[PKMAP_NR(vaddr)] < 2)
17		BUG();
18	spin_unlock(&kmap_lock);
19	return (void*) vaddr;
20}

 1void kunmap(struct page *page)
 2{
 3	if (in_interrupt())
 4		BUG();
 5	if (!PageHighMem(page))
 6		return;
 7	kunmap_high(page);
 8}
 9
10#define PKMAP_NR(virt)  ((virt-PKMAP_BASE) >> PAGE_SHIFT)
11
12void fastcall kunmap_high(struct page *page)
13{
14	unsigned long vaddr;
15	unsigned long nr;
16	int need_wakeup;
17
18	spin_lock(&kmap_lock);
19	vaddr = (unsigned long)page_address(page);
20	if (!vaddr)
21		BUG();
22	nr = PKMAP_NR(vaddr);
23
24	/*
25	 * A count must never go down to zero
26	 * without a TLB flush!
27	 */
28	need_wakeup = 0;
29	switch (--pkmap_count[nr]) {
30	case 0:
31		BUG();
32	case 1:
33		/*
34		 * Avoid an unnecessary wake_up() function call.
35		 * The common case is pkmap_count[] == 1, but
36		 * no waiters.
37		 * The tasks queued in the wait-queue are guarded
38		 * by both the lock in the wait-queue-head and by
39		 * the kmap_lock.  As the kmap_lock is held here,
40		 * no need for the wait-queue-head's lock.  Simply
41		 * test if the queue is empty.
42		 */
43		need_wakeup = waitqueue_active(&pkmap_map_wait);
44	}
45	spin_unlock(&kmap_lock);
46
47	/* do wake-up, if needed, race-free outside of the spin lock */
48	if (need_wakeup)
49		wake_up(&pkmap_map_wait);
50}

 1enum km_type {
 2D(0)	KM_BOUNCE_READ,
 3D(1)	KM_SKB_SUNRPC_DATA,
 4D(2)	KM_SKB_DATA_SOFTIRQ,
 5D(3)	KM_USER0,
 6D(4)	KM_USER1,
 7D(5)	KM_BIO_SRC_IRQ,
 8D(6)	KM_BIO_DST_IRQ,
 9D(7)	KM_PTE0,
10D(8)	KM_PTE1,
11D(9)	KM_IRQ0,
12D(10)	KM_IRQ1,
13D(11)	KM_SOFTIRQ0,
14D(12)	KM_SOFTIRQ1,
15D(13)	KM_TYPE_NR
16};

1#ifdef CONFIG_HIGHMEM
2	FIX_KMAP_BEGIN,	/* reserved pte's for temporary kernel mappings */
3	FIX_KMAP_END = FIX_KMAP_BEGIN+(KM_TYPE_NR*NR_CPUS)-1,
4#endif

 1#define __FIXADDR_TOP	0xfffff000
 2#define FIXADDR_TOP	((unsigned long)__FIXADDR_TOP)
 3#define __fix_to_virt(x)	(FIXADDR_TOP - ((x) << PAGE_SHIFT))
 4
 5/*
 6 * 'index to address' translation. If anyone tries to use the idx
 7 * directly without tranlation, we catch the bug with a NULL-deference
 8 * kernel oops. Illegal ranges of incoming indices are caught too.
 9 */
10static __always_inline unsigned long fix_to_virt(const unsigned int idx)
11{
12	/*
13	 * this branch gets completely eliminated after inlining,
14	 * except when someone tries to use fixaddr indices in an
15	 * illegal way. (such as mixing up address types or using
16	 * out-of-range indices).
17	 *
18	 * If it doesn't get removed, the linker will complain
19	 * loudly with a reasonably clear error message..
20	 */
21	if (idx >= __end_of_fixed_addresses)
22		__this_fixmap_does_not_exist();
23
24        return __fix_to_virt(idx);
25}

 1/*
 2 * kmap_atomic/kunmap_atomic is significantly faster than kmap/kunmap because
 3 * no global lock is needed and because the kmap code must perform a global TLB
 4 * invalidation when the kmap pool wraps.
 5 *
 6 * However when holding an atomic kmap is is not legal to sleep, so atomic
 7 * kmaps are appropriate for short, tight code paths only.
 8 */
 9void *kmap_atomic(struct page *page, enum km_type type)
10{
11	enum fixed_addresses idx;
12	unsigned long vaddr;
13
14	/* even !CONFIG_PREEMPT needs this, for in_atomic in do_page_fault */
15	inc_preempt_count();
16	if (!PageHighMem(page))
17		return page_address(page);
18
19	idx = type + KM_TYPE_NR*smp_processor_id();
20	vaddr = __fix_to_virt(FIX_KMAP_BEGIN + idx);
21#ifdef CONFIG_DEBUG_HIGHMEM
22	if (!pte_none(*(kmap_pte-idx)))
23		BUG();
24#endif
25	set_pte(kmap_pte-idx, mk_pte(page, kmap_prot));
26	__flush_tlb_one(vaddr);
27
28	return (void*) vaddr;
29}

1#define _PAGE_KERNEL \
2	(_PAGE_PRESENT | _PAGE_RW | _PAGE_DIRTY | _PAGE_ACCESSED | _PAGE_NX)

1void kunmap_atomic(void *kvaddr, enum km_type type)
2{
3	dec_preempt_count();
4	preempt_check_resched();
5}

1struct page		*zone_mem_map;

1struct free_area {
2	struct list_head	free_list;
3	unsigned long		nr_free;
4};
5
6struct free_area	free_area[MAX_ORDER];

 1/* 
 2 * Do the hard work of removing an element from the buddy allocator.
 3 * Call me with the zone->lock already held.
 4 */
 5static struct page *__rmqueue(struct zone *zone, unsigned int order)
 6{
 7	struct free_area * area;
 8	unsigned int current_order;
 9	struct page *page;
10
11	for (current_order = order; current_order < MAX_ORDER; ++current_order) {
12		area = zone->free_area + current_order;
13		if (list_empty(&area->free_list))
14			continue;
15
16		page = list_entry(area->free_list.next, struct page, lru);
17		list_del(&page->lru);
18		rmv_page_order(page);
19		area->nr_free--;
20		zone->free_pages -= 1UL << order;
21		return expand(zone, page, order, current_order, area);
22	}
23
24	return NULL;
25}

1#define __ClearPagePrivate(page) __clear_bit(PG_private, &(page)->flags)
2
3static inline void rmv_page_order(struct page *page)
4{
5	__ClearPagePrivate(page);
6	page->private = 0;
7}

 1static inline static inline void set_page_order(struct page *page, int order) {
 2	page->private = order;
 3	__SetPagePrivate(page);
 4}
 5
 6struct page *
 7expand(struct zone *zone, struct page *page,
 8 	int low, int high, struct free_area *area)
 9{
10	unsigned long size = 1 << high;
11
12	while (high > low) {
13		area--;
14		high--;
15		size >>= 1;
16		BUG_ON(bad_range(zone, &page[size]));
17		list_add(&page[size].lru, &area->free_list);
18		area->nr_free++;
19		set_page_order(&page[size], high);
20	}
21	return page;
22}

 1static inline void __free_pages_bulk (struct page *page, struct page *base,
 2		struct zone *zone, unsigned int order)
 3{
 4	unsigned long page_idx;
 5	struct page *coalesced;
 6	int order_size = 1 << order;
 7
 8	if (unlikely(order))
 9		destroy_compound_page(page, order);
10
11	page_idx = page - base;
12
13	BUG_ON(page_idx & (order_size - 1));
14	BUG_ON(bad_range(zone, page));
15
16	zone->free_pages += order_size;
17	while (order < MAX_ORDER-1) {
18		struct free_area *area;
19		struct page *buddy;
20		int buddy_idx;
21
22		buddy_idx = (page_idx ^ (1 << order));
23		buddy = base + buddy_idx;
24		if (bad_range(zone, buddy))
25			break;
26		if (!page_is_buddy(buddy, order))
27			break;
28		/* Move the buddy up one level. */
29		list_del(&buddy->lru);
30		area = zone->free_area + order;
31		area->nr_free--;
32		rmv_page_order(buddy);
33		page_idx &= buddy_idx;
34		order++;
35	}
36	coalesced = base + page_idx;
37	set_page_order(coalesced, order);
38	list_add(&coalesced->lru, &zone->free_area[order].free_list);
39	zone->free_area[order].nr_free++;
40}

 1#ifndef CONFIG_HUGETLB_PAGE
 2#define PageCompound(page)	0
 3#define destroy_compound_page(page, order) do { } while (0)
 4
 5#else
 6#define PageCompound(page)	test_bit(PG_compound, &(page)->flags)
 7static void destroy_compound_page(struct page *page, unsigned long order)
 8{
 9	int i;
10	int nr_pages = 1 << order;
11
12	if (!PageCompound(page))
13		return;
14
15	if (page[1].index != order)
16		bad_page(__FUNCTION__, page);
17
18	for (i = 0; i < nr_pages; i++) {
19		struct page *p = page + i;
20
21		if (!PageCompound(p))
22			bad_page(__FUNCTION__, page);
23		if (p->private != (unsigned long)page)
24			bad_page(__FUNCTION__, page);
25		ClearPageCompound(p);
26	}
27}
28#endif		/* CONFIG_HUGETLB_PAGE */

 1/*
 2 * Temporary debugging check for pages not lying within a given zone.
 3 */
 4static int bad_range(struct zone *zone, struct page *page)
 5{
 6	if (page_to_pfn(page) >= zone->zone_start_pfn + zone->spanned_pages)
 7		return 1;
 8	if (page_to_pfn(page) < zone->zone_start_pfn)
 9		return 1;
10#ifdef CONFIG_HOLES_IN_ZONE
11	if (!pfn_valid(page_to_pfn(page)))
12		return 1;
13#endif
14	if (zone != page_zone(page))
15		return 1;
16	return 0;
17}
18
19/*
20 * This function checks whether a page is free && is the buddy
21 * we can do coalesce a page and its buddy if
22 * (a) the buddy is free &&
23 * (b) the buddy is on the buddy system &&
24 * (c) a page and its buddy have the same order.
25 * for recording page's order, we use page->private and PG_private.
26 *
27 */
28static inline int page_is_buddy(struct page *page, int order)
29{
30       if (PagePrivate(page)           &&
31           (page_order(page) == order) &&
32           !PageReserved(page)         &&
33            page_count(page) == 0)
34               return 1;
35       return 0;
36}

 1struct per_cpu_pages {
 2	int count;		/* number of pages in the list */
 3	int low;		/* low watermark, refill needed */
 4	int high;		/* high watermark, emptying needed */
 5	int batch;		/* chunk size for buddy add/remove */
 6	struct list_head list;	/* the list of pages */
 7};
 8
 9struct per_cpu_pageset {
10	struct per_cpu_pages pcp[2];	/* 0: hot.  1: cold */
11#ifdef CONFIG_NUMA
12	unsigned long numa_hit;		/* allocated in intended node */
13	unsigned long numa_miss;	/* allocated in non intended node */
14	unsigned long numa_foreign;	/* was intended here, hit elsewhere */
15	unsigned long interleave_hit; 	/* interleaver prefered this zone */
16	unsigned long local_node;	/* allocation from local node */
17	unsigned long other_node;	/* allocation from other node */
18#endif
19} ____cacheline_aligned_in_smp;

 1/*
 2 * Really, prep_compound_page() should be called from __rmqueue_bulk().  But
 3 * we cheat by calling it from here, in the order > 0 path.  Saves a branch
 4 * or two.
 5 */
 6static struct page *
 7buffered_rmqueue(struct zone *zone, int order, int gfp_flags)
 8{
 9	unsigned long flags;
10	struct page *page = NULL;
11	int cold = !!(gfp_flags & __GFP_COLD);
12
13	if (order == 0) {
14		struct per_cpu_pages *pcp;
15
16		pcp = &zone->pageset[get_cpu()].pcp[cold];
17		local_irq_save(flags);
18		if (pcp->count <= pcp->low)
19			pcp->count += rmqueue_bulk(zone, 0,
20						pcp->batch, &pcp->list);
21		if (pcp->count) {
22			page = list_entry(pcp->list.next, struct page, lru);
23			list_del(&page->lru);
24			pcp->count--;
25		}
26		local_irq_restore(flags);
27		put_cpu();
28	}
29
30	if (page == NULL) {
31		spin_lock_irqsave(&zone->lock, flags);
32		page = __rmqueue(zone, order);
33		spin_unlock_irqrestore(&zone->lock, flags);
34	}
35
36	if (page != NULL) {
37		BUG_ON(bad_range(zone, page));
38		mod_page_state_zone(zone, pgalloc, 1 << order);
39		prep_new_page(page, order);
40
41		if (gfp_flags & __GFP_ZERO)
42			prep_zero_page(page, order, gfp_flags);
43
44		if (order && (gfp_flags & __GFP_COMP))
45			prep_compound_page(page, order);
46	}
47	return page;
48}

1void fastcall free_hot_page(struct page *page)
2{
3	free_hot_cold_page(page, 0);
4}
5	
6void fastcall free_cold_page(struct page *page)
7{
8	free_hot_cold_page(page, 1);
9}

 1static void fastcall free_hot_cold_page(struct page *page, int cold)
 2{
 3	struct zone *zone = page_zone(page);
 4	struct per_cpu_pages *pcp;
 5	unsigned long flags;
 6
 7	arch_free_page(page, 0);
 8
 9	kernel_map_pages(page, 1, 0);
10	inc_page_state(pgfree);
11	if (PageAnon(page))
12		page->mapping = NULL;
13	free_pages_check(__FUNCTION__, page);
14	pcp = &zone->pageset[get_cpu()].pcp[cold];
15	local_irq_save(flags);
16	if (pcp->count >= pcp->high)
17		pcp->count -= free_pages_bulk(zone, pcp->batch, &pcp->list, 0);
18	list_add(&page->lru, &pcp->list);
19	pcp->count++;
20	local_irq_restore(flags);
21	put_cpu();
22}

 1void __mod_page_state(unsigned offset, unsigned long delta)
 2{
 3	unsigned long flags;
 4	void* ptr;
 5
 6	local_irq_save(flags);
 7	ptr = &__get_cpu_var(page_states);
 8	*(unsigned long*)(ptr + offset) += delta;
 9	local_irq_restore(flags);
10}
11
12#define mod_page_state(member, delta)	\
13	__mod_page_state(offsetof(struct page_state, member), (delta))
14#define inc_page_state(member)	mod_page_state(member, 1UL)

 1static inline void free_pages_check(const char *function, struct page *page)
 2{
 3	if (	page_mapped(page) ||
 4		page->mapping != NULL ||
 5		page_count(page) != 0 ||
 6		(page->flags & (
 7			1 << PG_lru	|
 8			1 << PG_private |
 9			1 << PG_locked	|
10			1 << PG_active	|
11			1 << PG_reclaim	|
12			1 << PG_slab	|
13			1 << PG_swapcache |
14			1 << PG_writeback )))
15		bad_page(function, page);
16	if (PageDirty(page))
17		ClearPageDirty(page);
18}

 1/*
 2 * Frees a list of pages. 
 3 * Assumes all pages on list are in same zone, and of same order.
 4 * count is the number of pages to free, or 0 for all on the list.
 5 *
 6 * If the zone was previously in an "all pages pinned" state then look to
 7 * see if this freeing clears that state.
 8 *
 9 * And clear the zone's pages_scanned counter, to hold off the "all pages are
10 * pinned" detection logic.
11 */
12static int
13free_pages_bulk(struct zone *zone, int count,
14		struct list_head *list, unsigned int order)
15{
16	unsigned long flags;
17	struct page *base, *page = NULL;
18	int ret = 0;
19
20	base = zone->zone_mem_map;
21	spin_lock_irqsave(&zone->lock, flags);
22	zone->all_unreclaimable = 0;
23	zone->pages_scanned = 0;
24	while (!list_empty(list) && count--) {
25		page = list_entry(list->prev, struct page, lru);
26		/* have to delete it as __free_pages_bulk list manipulates */
27		list_del(&page->lru);
28		__free_pages_bulk(page, base, zone, order);
29		ret++;
30	}
31	spin_unlock_irqrestore(&zone->lock, flags);
32	return ret;
33}

  1/*
  2 * This is the 'heart' of the zoned buddy allocator.
  3 */
  4struct page * fastcall
  5__alloc_pages(unsigned int gfp_mask, unsigned int order,
  6		struct zonelist *zonelist)
  7{
  8	const int wait = gfp_mask & __GFP_WAIT;
  9	struct zone **zones, *z;
 10	struct page *page;
 11	struct reclaim_state reclaim_state;
 12	struct task_struct *p = current;
 13	int i;
 14	int classzone_idx;
 15	int do_retry;
 16	int can_try_harder;
 17	int did_some_progress;
 18
 19	might_sleep_if(wait);
 20
 21	/*
 22	 * The caller may dip into page reserves a bit more if the caller
 23	 * cannot run direct reclaim, or is the caller has realtime scheduling
 24	 * policy
 25	 */
 26	can_try_harder = (unlikely(rt_task(p)) && !in_interrupt()) || !wait;
 27
 28	zones = zonelist->zones;  /* the list of zones suitable for gfp_mask */
 29
 30	if (unlikely(zones[0] == NULL)) {
 31		/* Should this ever happen?? */
 32		return NULL;
 33	}
 34
 35	classzone_idx = zone_idx(zones[0]);
 36
 37 restart:
 38	/* Go through the zonelist once, looking for a zone with enough free */
 39	for (i = 0; (z = zones[i]) != NULL; i++) {
 40
 41		if (!zone_watermark_ok(z, order, z->pages_low,
 42				       classzone_idx, 0, 0))
 43			continue;
 44
 45		page = buffered_rmqueue(z, order, gfp_mask);
 46		if (page)
 47			goto got_pg;
 48	}
 49
 50	for (i = 0; (z = zones[i]) != NULL; i++)
 51		wakeup_kswapd(z, order);
 52
 53	/*
 54	 * Go through the zonelist again. Let __GFP_HIGH and allocations
 55	 * coming from realtime tasks to go deeper into reserves
 56	 */
 57	for (i = 0; (z = zones[i]) != NULL; i++) {
 58		if (!zone_watermark_ok(z, order, z->pages_min,
 59				       classzone_idx, can_try_harder,
 60				       gfp_mask & __GFP_HIGH))
 61			continue;
 62
 63		page = buffered_rmqueue(z, order, gfp_mask);
 64		if (page)
 65			goto got_pg;
 66	}
 67
 68	/* This allocation should allow future memory freeing. */
 69	if (((p->flags & PF_MEMALLOC) || unlikely(test_thread_flag(TIF_MEMDIE))) && !in_interrupt()) {
 70		/* go through the zonelist yet again, ignoring mins */
 71		for (i = 0; (z = zones[i]) != NULL; i++) {
 72			page = buffered_rmqueue(z, order, gfp_mask);
 73			if (page)
 74				goto got_pg;
 75		}
 76		goto nopage;
 77	}
 78
 79	/* Atomic allocations - we can't balance anything */
 80	if (!wait)
 81		goto nopage;
 82
 83rebalance:
 84	cond_resched();
 85
 86	/* We now go into synchronous reclaim */
 87	p->flags |= PF_MEMALLOC;
 88	reclaim_state.reclaimed_slab = 0;
 89	p->reclaim_state = &reclaim_state;
 90
 91	did_some_progress = try_to_free_pages(zones, gfp_mask, order);
 92
 93	p->reclaim_state = NULL;
 94	p->flags &= ~PF_MEMALLOC;
 95
 96	cond_resched();
 97
 98	if (likely(did_some_progress)) {
 99		/*
100		 * Go through the zonelist yet one more time, keep
101		 * very high watermark here, this is only to catch
102		 * a parallel oom killing, we must fail if we're still
103		 * under heavy pressure.
104		 */
105		for (i = 0; (z = zones[i]) != NULL; i++) {
106			if (!zone_watermark_ok(z, order, z->pages_min,
107					       classzone_idx, can_try_harder,
108					       gfp_mask & __GFP_HIGH))
109				continue;
110
111			page = buffered_rmqueue(z, order, gfp_mask);
112			if (page)
113				goto got_pg;
114		}
115	} else if ((gfp_mask & __GFP_FS) && !(gfp_mask & __GFP_NORETRY)) {
116		/*
117		 * Go through the zonelist yet one more time, keep
118		 * very high watermark here, this is only to catch
119		 * a parallel oom killing, we must fail if we're still
120		 * under heavy pressure.
121		 */
122		for (i = 0; (z = zones[i]) != NULL; i++) {
123			if (!zone_watermark_ok(z, order, z->pages_high,
124					       classzone_idx, 0, 0))
125				continue;
126
127			page = buffered_rmqueue(z, order, gfp_mask);
128			if (page)
129				goto got_pg;
130		}
131
132		out_of_memory(gfp_mask);
133		goto restart;
134	}
135
136	/*
137	 * Don't let big-order allocations loop unless the caller explicitly
138	 * requests that.  Wait for some write requests to complete then retry.
139	 *
140	 * In this implementation, __GFP_REPEAT means __GFP_NOFAIL for order
141	 * <= 3, but that may not be true in other implementations.
142	 */
143	do_retry = 0;
144	if (!(gfp_mask & __GFP_NORETRY)) {
145		if ((order <= 3) || (gfp_mask & __GFP_REPEAT))
146			do_retry = 1;
147		if (gfp_mask & __GFP_NOFAIL)
148			do_retry = 1;
149	}
150	if (do_retry) {
151		blk_congestion_wait(WRITE, HZ/50);
152		goto rebalance;
153	}
154
155nopage:
156	if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit()) {
157		printk(KERN_WARNING "%s: page allocation failure."
158			" order:%d, mode:0x%x\n",
159			p->comm, order, gfp_mask);
160		dump_stack();
161	}
162	return NULL;
163got_pg:
164	zone_statistics(zonelist, z);
165	return page;
166}

1fastcall void __free_pages(struct page *page, unsigned int order)
2{
3	if (!PageReserved(page) && put_page_testzero(page)) {
4		if (order == 0)
5			free_hot_page(page);
6		else
7			__free_pages_ok(page, order);
8	}
9}

 1/* flags for kmem_cache_alloc() */
 2#define	SLAB_NOFS		GFP_NOFS
 3#define	SLAB_NOIO		GFP_NOIO
 4#define	SLAB_ATOMIC		GFP_ATOMIC
 5#define	SLAB_USER		GFP_USER
 6#define	SLAB_KERNEL		GFP_KERNEL
 7#define	SLAB_DMA		GFP_DMA
 8
 9#define SLAB_LEVEL_MASK		GFP_LEVEL_MASK
10
11#define	SLAB_NO_GROW		__GFP_NO_GROW	/* don't grow a cache */
12
13/* flags to pass to kmem_cache_create().
14 * The first 3 are only valid when the allocator as been build
15 * SLAB_DEBUG_SUPPORT.
16 */
17#define	SLAB_DEBUG_FREE		0x00000100UL	/* Peform (expensive) checks on free */
18#define	SLAB_DEBUG_INITIAL	0x00000200UL	/* Call constructor (as verifier) */
19#define	SLAB_RED_ZONE		0x00000400UL	/* Red zone objs in a cache */
20#define	SLAB_POISON		0x00000800UL	/* Poison objects */
21#define	SLAB_NO_REAP		0x00001000UL	/* never reap from the cache */
22#define	SLAB_HWCACHE_ALIGN	0x00002000UL	/* align objs on a h/w cache lines */
23#define SLAB_CACHE_DMA		0x00004000UL	/* use GFP_DMA memory */
24#define SLAB_MUST_HWCACHE_ALIGN	0x00008000UL	/* force alignment */
25#define SLAB_STORE_USER		0x00010000UL	/* store the last owner for bug hunting */
26#define SLAB_RECLAIM_ACCOUNT	0x00020000UL	/* track pages allocated to indicate
27						   what is reclaimable later*/
28#define SLAB_PANIC		0x00040000UL	/* panic if kmem_cache_create() fails */
29#define SLAB_DESTROY_BY_RCU	0x00080000UL	/* defer freeing pages to RCU */
30
31/* flags passed to a constructor func */
32#define	SLAB_CTOR_CONSTRUCTOR	0x001UL		/* if not set, then deconstructor */
33#define SLAB_CTOR_ATOMIC	0x002UL		/* tell constructor it can't sleep */
34#define	SLAB_CTOR_VERIFY	0x004UL		/* tell constructor it's a verify call */

 1/**
 2 * kmem_cache_create - Create a cache.
 3 * @name: A string which is used in /proc/slabinfo to identify this cache.
 4 * @size: The size of objects to be created in this cache.
 5 * @align: The required alignment for the objects.
 6 * @flags: SLAB flags
 7 * @ctor: A constructor for the objects.
 8 * @dtor: A destructor for the objects.
 9 *
10 * Returns a ptr to the cache on success, NULL on failure.
11 * Cannot be called within a int, but can be interrupted.
12 * The @ctor is run when new pages are allocated by the cache
13 * and the @dtor is run before the pages are handed back.
14 *
15 * @name must be valid until the cache is destroyed. This implies that
16 * the module calling this has to destroy the cache before getting 
17 * unloaded.
18 * 
19 * The flags are
20 *
21 * %SLAB_POISON - Poison the slab with a known test pattern (a5a5a5a5)
22 * to catch references to uninitialised memory.
23 *
24 * %SLAB_RED_ZONE - Insert `Red' zones around the allocated memory to check
25 * for buffer overruns.
26 *
27 * %SLAB_NO_REAP - Don't automatically reap this cache when we're under
28 * memory pressure.
29 *
30 * %SLAB_HWCACHE_ALIGN - Align the objects in this cache to a hardware
31 * cacheline.  This can be beneficial if you're counting cycles as closely
32 * as davem.
33 */
34kmem_cache_t *
35kmem_cache_create (const char *name, size_t size, size_t align,
36	unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
37	void (*dtor)(void*, kmem_cache_t *, unsigned long))

1...
2	cachep->colour_off = cache_line_size();
3	/* Offset must be a multiple of the alignment. */
4	if (cachep->colour_off < align)
5		cachep->colour_off = align;
6	cachep->colour = left_over/cachep->colour_off;
7...

 1/*
 2 * struct array_cache
 3 *
 4 * Per cpu structures
 5 * Purpose:
 6 * - LIFO ordering, to hand out cache-warm objects from _alloc
 7 * - reduce the number of linked list operations
 8 * - reduce spinlock operations
 9 *
10 * The limit is stored in the per-cpu structure to reduce the data cache
11 * footprint.
12 *
13 */
14struct array_cache {
15	unsigned int avail;
16	unsigned int limit;
17	unsigned int batchcount;
18	unsigned int touched;
19};

 1/*
 2 * Interface to system's page allocator. No need to hold the cache-lock.
 3 *
 4 * If we requested dmaable memory, we will get it. Even if we
 5 * did not request dmaable memory, we might get it, but that
 6 * would be relatively rare and ignorable.
 7 */
 8static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
 9{
10	struct page *page;
11	void *addr;
12	int i;
13
14	flags |= cachep->gfpflags;
15	if (likely(nodeid == -1)) {
16		page = alloc_pages(flags, cachep->gfporder);
17	} else {
18		page = alloc_pages_node(nodeid, flags, cachep->gfporder);
19	}
20	if (!page)
21		return NULL;
22	addr = page_address(page);
23
24	i = (1 << cachep->gfporder);
25	if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
26		atomic_add(i, &slab_reclaim_pages);
27	add_page_state(nr_slab, i);
28	while (i--) {
29		SetPageSlab(page);
30		page++;
31	}
32	return addr;
33}

 1/*
 2 * Interface to system's page release.
 3 */
 4static void kmem_freepages(kmem_cache_t *cachep, void *addr)
 5{
 6	unsigned long i = (1<<cachep->gfporder);
 7	struct page *page = virt_to_page(addr);
 8	const unsigned long nr_freed = i;
 9
10	while (i--) {
11		if (!TestClearPageSlab(page))
12			BUG();
13		page++;
14	}
15	sub_page_state(nr_slab, nr_freed);
16	if (current->reclaim_state)
17		current->reclaim_state->reclaimed_slab += nr_freed;
18	free_pages((unsigned long)addr, cachep->gfporder);
19	if (cachep->flags & SLAB_RECLAIM_ACCOUNT) 
20		atomic_sub(1<<cachep->gfporder, &slab_reclaim_pages);
21}

 1/*
 2 * Grow (by 1) the number of slabs within a cache.  This is called by
 3 * kmem_cache_alloc() when there are no active objs left in a cache.
 4 */
 5static int cache_grow (kmem_cache_t * cachep, int flags, int nodeid)
 6{
 7	struct slab	*slabp;
 8	void		*objp;
 9	size_t		 offset;
10	int		 local_flags;
11	unsigned long	 ctor_flags;
12
13	/* Be lazy and only check for valid flags here,
14 	 * keeping it out of the critical path in kmem_cache_alloc().
15	 */
16	if (flags & ~(SLAB_DMA|SLAB_LEVEL_MASK|SLAB_NO_GROW))
17		BUG();
18	if (flags & SLAB_NO_GROW)
19		return 0;
20
21	ctor_flags = SLAB_CTOR_CONSTRUCTOR;
22	local_flags = (flags & SLAB_LEVEL_MASK);
23	if (!(local_flags & __GFP_WAIT))
24		/*
25		 * Not allowed to sleep.  Need to tell a constructor about
26		 * this - it might need to know...
27		 */
28		ctor_flags |= SLAB_CTOR_ATOMIC;
29
30	/* About to mess with non-constant members - lock. */
31	check_irq_off();
32	spin_lock(&cachep->spinlock);
33
34	/* Get colour for the slab, and cal the next value. */
35	offset = cachep->colour_next;
36	cachep->colour_next++;
37	if (cachep->colour_next >= cachep->colour)
38		cachep->colour_next = 0;
39	offset *= cachep->colour_off;
40
41	spin_unlock(&cachep->spinlock);
42
43	if (local_flags & __GFP_WAIT)
44		local_irq_enable();
45
46	/*
47	 * The test for missing atomic flag is performed here, rather than
48	 * the more obvious place, simply to reduce the critical path length
49	 * in kmem_cache_alloc(). If a caller is seriously mis-behaving they
50	 * will eventually be caught here (where it matters).
51	 */
52	kmem_flagcheck(cachep, flags);
53
54
55	/* Get mem for the objs. */
56	if (!(objp = kmem_getpages(cachep, flags, nodeid)))
57		goto failed;
58
59	/* Get slab management. */
60	if (!(slabp = alloc_slabmgmt(cachep, objp, offset, local_flags)))
61		goto opps1;
62
63	set_slab_attr(cachep, slabp, objp);
64
65	cache_init_objs(cachep, slabp, ctor_flags);
66
67	if (local_flags & __GFP_WAIT)
68		local_irq_disable();
69	check_irq_off();
70	spin_lock(&cachep->spinlock);
71
72	/* Make slab active. */
73	list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_free));
74	STATS_INC_GROWN(cachep);
75	list3_data(cachep)->free_objects += cachep->num;
76	spin_unlock(&cachep->spinlock);
77	return 1;
78opps1:
79	kmem_freepages(cachep, objp);
80failed:
81	if (local_flags & __GFP_WAIT)
82		local_irq_disable();
83	return 0;
84}