Kernel

Kernel Git Source Tree

Root/mm/compaction.c

1	/*
2	* linux/mm/compaction.c
3	*
4	* Memory compaction for the reduction of external fragmentation. Note that
5	* this heavily depends upon page migration to do all the real heavy
6	* lifting
7	*
8	* Copyright IBM Corp. 2007-2010 Mel Gorman <mel@csn.ul.ie>
9	*/
10	#include <linux/swap.h>
11	#include <linux/migrate.h>
12	#include <linux/compaction.h>
13	#include <linux/mm_inline.h>
14	#include <linux/backing-dev.h>
15	#include <linux/sysctl.h>
16	#include <linux/sysfs.h>
17	#include <linux/balloon_compaction.h>
18	#include <linux/page-isolation.h>
19	#include "internal.h"
20
21	#ifdef CONFIG_COMPACTION
22	static inline void count_compact_event(enum vm_event_item item)
23	{
24	count_vm_event(item);
25	}
26
27	static inline void count_compact_events(enum vm_event_item item, long delta)
28	{
29	count_vm_events(item, delta);
30	}
31	#else
32	#define count_compact_event(item) do { } while (0)
33	#define count_compact_events(item, delta) do { } while (0)
34	#endif
35
36	#if defined CONFIG_COMPACTION \|\| defined CONFIG_CMA
37
38	#define CREATE_TRACE_POINTS
39	#include <trace/events/compaction.h>
40
41	static unsigned long release_freepages(struct list_head *freelist)
42	{
43	struct page page, next;
44	unsigned long count = 0;
45
46	list_for_each_entry_safe(page, next, freelist, lru) {
47	list_del(&page->lru);
48	__free_page(page);
49	count++;
50	}
51
52	return count;
53	}
54
55	static void map_pages(struct list_head *list)
56	{
57	struct page *page;
58
59	list_for_each_entry(page, list, lru) {
60	arch_alloc_page(page, 0);
61	kernel_map_pages(page, 1, 1);
62	}
63	}
64
65	static inline bool migrate_async_suitable(int migratetype)
66	{
67	return is_migrate_cma(migratetype) \|\| migratetype == MIGRATE_MOVABLE;
68	}
69
70	#ifdef CONFIG_COMPACTION
71	/* Returns true if the pageblock should be scanned for pages to isolate. */
72	static inline bool isolation_suitable(struct compact_control *cc,
73	struct page *page)
74	{
75	if (cc->ignore_skip_hint)
76	return true;
77
78	return !get_pageblock_skip(page);
79	}
80
81	/*
82	* This function is called to clear all cached information on pageblocks that
83	* should be skipped for page isolation when the migrate and free page scanner
84	* meet.
85	*/
86	static void __reset_isolation_suitable(struct zone *zone)
87	{
88	unsigned long start_pfn = zone->zone_start_pfn;
89	unsigned long end_pfn = zone_end_pfn(zone);
90	unsigned long pfn;
91
92	zone->compact_cached_migrate_pfn = start_pfn;
93	zone->compact_cached_free_pfn = end_pfn;
94	zone->compact_blockskip_flush = false;
95
96	/* Walk the zone and mark every pageblock as suitable for isolation */
97	for (pfn = start_pfn; pfn < end_pfn; pfn += pageblock_nr_pages) {
98	struct page *page;
99
100	cond_resched();
101
102	if (!pfn_valid(pfn))
103	continue;
104
105	page = pfn_to_page(pfn);
106	if (zone != page_zone(page))
107	continue;
108
109	clear_pageblock_skip(page);
110	}
111	}
112
113	void reset_isolation_suitable(pg_data_t *pgdat)
114	{
115	int zoneid;
116
117	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
118	struct zone *zone = &pgdat->node_zones[zoneid];
119	if (!populated_zone(zone))
120	continue;
121
122	/* Only flush if a full compaction finished recently */
123	if (zone->compact_blockskip_flush)
124	__reset_isolation_suitable(zone);
125	}
126	}
127
128	/*
129	* If no pages were isolated then mark this pageblock to be skipped in the
130	* future. The information is later cleared by __reset_isolation_suitable().
131	*/
132	static void update_pageblock_skip(struct compact_control *cc,
133	struct page *page, unsigned long nr_isolated,
134	bool migrate_scanner)
135	{
136	struct zone *zone = cc->zone;
137	if (!page)
138	return;
139
140	if (!nr_isolated) {
141	unsigned long pfn = page_to_pfn(page);
142	set_pageblock_skip(page);
143
144	/* Update where compaction should restart */
145	if (migrate_scanner) {
146	if (!cc->finished_update_migrate &&
147	pfn > zone->compact_cached_migrate_pfn)
148	zone->compact_cached_migrate_pfn = pfn;
149	} else {
150	if (!cc->finished_update_free &&
151	pfn < zone->compact_cached_free_pfn)
152	zone->compact_cached_free_pfn = pfn;
153	}
154	}
155	}
156	#else
157	static inline bool isolation_suitable(struct compact_control *cc,
158	struct page *page)
159	{
160	return true;
161	}
162
163	static void update_pageblock_skip(struct compact_control *cc,
164	struct page *page, unsigned long nr_isolated,
165	bool migrate_scanner)
166	{
167	}
168	#endif /* CONFIG_COMPACTION */
169
170	static inline bool should_release_lock(spinlock_t *lock)
171	{
172	return need_resched() \|\| spin_is_contended(lock);
173	}
174
175	/*
176	* Compaction requires the taking of some coarse locks that are potentially
177	* very heavily contended. Check if the process needs to be scheduled or
178	* if the lock is contended. For async compaction, back out in the event
179	* if contention is severe. For sync compaction, schedule.
180	*
181	* Returns true if the lock is held.
182	* Returns false if the lock is released and compaction should abort
183	*/
184	static bool compact_checklock_irqsave(spinlock_t lock, unsigned long flags,
185	bool locked, struct compact_control *cc)
186	{
187	if (should_release_lock(lock)) {
188	if (locked) {
189	spin_unlock_irqrestore(lock, *flags);
190	locked = false;
191	}
192
193	/* async aborts if taking too long or contended */
194	if (!cc->sync) {
195	cc->contended = true;
196	return false;
197	}
198
199	cond_resched();
200	}
201
202	if (!locked)
203	spin_lock_irqsave(lock, *flags);
204	return true;
205	}
206
207	static inline bool compact_trylock_irqsave(spinlock_t *lock,
208	unsigned long flags, struct compact_control cc)
209	{
210	return compact_checklock_irqsave(lock, flags, false, cc);
211	}
212
213	/* Returns true if the page is within a block suitable for migration to */
214	static bool suitable_migration_target(struct page *page)
215	{
216	int migratetype = get_pageblock_migratetype(page);
217
218	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
219	if (migratetype == MIGRATE_RESERVE)
220	return false;
221
222	if (is_migrate_isolate(migratetype))
223	return false;
224
225	/* If the page is a large free page, then allow migration */
226	if (PageBuddy(page) && page_order(page) >= pageblock_order)
227	return true;
228
229	/* If the block is MIGRATE_MOVABLE or MIGRATE_CMA, allow migration */
230	if (migrate_async_suitable(migratetype))
231	return true;
232
233	/* Otherwise skip the block */
234	return false;
235	}
236
237	/*
238	* Isolate free pages onto a private freelist. Caller must hold zone->lock.
239	* If @strict is true, will abort returning 0 on any invalid PFNs or non-free
240	* pages inside of the pageblock (even though it may still end up isolating
241	* some pages).
242	*/
243	static unsigned long isolate_freepages_block(struct compact_control *cc,
244	unsigned long blockpfn,
245	unsigned long end_pfn,
246	struct list_head *freelist,
247	bool strict)
248	{
249	int nr_scanned = 0, total_isolated = 0;
250	struct page cursor, valid_page = NULL;
251	unsigned long nr_strict_required = end_pfn - blockpfn;
252	unsigned long flags;
253	bool locked = false;
254
255	cursor = pfn_to_page(blockpfn);
256
257	/* Isolate free pages. */
258	for (; blockpfn < end_pfn; blockpfn++, cursor++) {
259	int isolated, i;
260	struct page *page = cursor;
261
262	nr_scanned++;
263	if (!pfn_valid_within(blockpfn))
264	continue;
265	if (!valid_page)
266	valid_page = page;
267	if (!PageBuddy(page))
268	continue;
269
270	/*
271	* The zone lock must be held to isolate freepages.
272	* Unfortunately this is a very coarse lock and can be
273	* heavily contended if there are parallel allocations
274	* or parallel compactions. For async compaction do not
275	* spin on the lock and we acquire the lock as late as
276	* possible.
277	*/
278	locked = compact_checklock_irqsave(&cc->zone->lock, &flags,
279	locked, cc);
280	if (!locked)
281	break;
282
283	/* Recheck this is a suitable migration target under lock */
284	if (!strict && !suitable_migration_target(page))
285	break;
286
287	/* Recheck this is a buddy page under lock */
288	if (!PageBuddy(page))
289	continue;
290
291	/* Found a free page, break it into order-0 pages */
292	isolated = split_free_page(page);
293	if (!isolated && strict)
294	break;
295	total_isolated += isolated;
296	for (i = 0; i < isolated; i++) {
297	list_add(&page->lru, freelist);
298	page++;
299	}
300
301	/* If a page was split, advance to the end of it */
302	if (isolated) {
303	blockpfn += isolated - 1;
304	cursor += isolated - 1;
305	}
306	}
307
308	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
309
310	/*
311	* If strict isolation is requested by CMA then check that all the
312	* pages requested were isolated. If there were any failures, 0 is
313	* returned and CMA will fail.
314	*/
315	if (strict && nr_strict_required > total_isolated)
316	total_isolated = 0;
317
318	if (locked)
319	spin_unlock_irqrestore(&cc->zone->lock, flags);
320
321	/* Update the pageblock-skip if the whole pageblock was scanned */
322	if (blockpfn == end_pfn)
323	update_pageblock_skip(cc, valid_page, total_isolated, false);
324
325	count_compact_events(COMPACTFREE_SCANNED, nr_scanned);
326	if (total_isolated)
327	count_compact_events(COMPACTISOLATED, total_isolated);
328	return total_isolated;
329	}
330
331	/**
332	* isolate_freepages_range() - isolate free pages.
333	* @start_pfn: The first PFN to start isolating.
334	* @end_pfn: The one-past-last PFN.
335	*
336	* Non-free pages, invalid PFNs, or zone boundaries within the
337	* [start_pfn, end_pfn) range are considered errors, cause function to
338	* undo its actions and return zero.
339	*
340	* Otherwise, function returns one-past-the-last PFN of isolated page
341	* (which may be greater then end_pfn if end fell in a middle of
342	* a free page).
343	*/
344	unsigned long
345	isolate_freepages_range(struct compact_control *cc,
346	unsigned long start_pfn, unsigned long end_pfn)
347	{
348	unsigned long isolated, pfn, block_end_pfn;
349	LIST_HEAD(freelist);
350
351	for (pfn = start_pfn; pfn < end_pfn; pfn += isolated) {
352	if (!pfn_valid(pfn) \|\| cc->zone != page_zone(pfn_to_page(pfn)))
353	break;
354
355	/*
356	* On subsequent iterations ALIGN() is actually not needed,
357	* but we keep it that we not to complicate the code.
358	*/
359	block_end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
360	block_end_pfn = min(block_end_pfn, end_pfn);
361
362	isolated = isolate_freepages_block(cc, pfn, block_end_pfn,
363	&freelist, true);
364
365	/*
366	* In strict mode, isolate_freepages_block() returns 0 if
367	* there are any holes in the block (ie. invalid PFNs or
368	* non-free pages).
369	*/
370	if (!isolated)
371	break;
372
373	/*
374	* If we managed to isolate pages, it is always (1 << n) *
375	* pageblock_nr_pages for some non-negative n. (Max order
376	* page may span two pageblocks).
377	*/
378	}
379
380	/* split_free_page does not map the pages */
381	map_pages(&freelist);
382
383	if (pfn < end_pfn) {
384	/* Loop terminated early, cleanup. */
385	release_freepages(&freelist);
386	return 0;
387	}
388
389	/* We don't use freelists for anything. */
390	return pfn;
391	}
392
393	/* Update the number of anon and file isolated pages in the zone */
394	static void acct_isolated(struct zone zone, bool locked, struct compact_control cc)
395	{
396	struct page *page;
397	unsigned int count[2] = { 0, };
398
399	list_for_each_entry(page, &cc->migratepages, lru)
400	count[!!page_is_file_cache(page)]++;
401
402	/* If locked we can use the interrupt unsafe versions */
403	if (locked) {
404	__mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
405	__mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
406	} else {
407	mod_zone_page_state(zone, NR_ISOLATED_ANON, count[0]);
408	mod_zone_page_state(zone, NR_ISOLATED_FILE, count[1]);
409	}
410	}
411
412	/* Similar to reclaim, but different enough that they don't share logic */
413	static bool too_many_isolated(struct zone *zone)
414	{
415	unsigned long active, inactive, isolated;
416
417	inactive = zone_page_state(zone, NR_INACTIVE_FILE) +
418	zone_page_state(zone, NR_INACTIVE_ANON);
419	active = zone_page_state(zone, NR_ACTIVE_FILE) +
420	zone_page_state(zone, NR_ACTIVE_ANON);
421	isolated = zone_page_state(zone, NR_ISOLATED_FILE) +
422	zone_page_state(zone, NR_ISOLATED_ANON);
423
424	return isolated > (inactive + active) / 2;
425	}
426
427	/**
428	* isolate_migratepages_range() - isolate all migrate-able pages in range.
429	* @zone: Zone pages are in.
430	* @cc: Compaction control structure.
431	* @low_pfn: The first PFN of the range.
432	* @end_pfn: The one-past-the-last PFN of the range.
433	* @unevictable: true if it allows to isolate unevictable pages
434	*
435	* Isolate all pages that can be migrated from the range specified by
436	* [low_pfn, end_pfn). Returns zero if there is a fatal signal
437	* pending), otherwise PFN of the first page that was not scanned
438	* (which may be both less, equal to or more then end_pfn).
439	*
440	* Assumes that cc->migratepages is empty and cc->nr_migratepages is
441	* zero.
442	*
443	* Apart from cc->migratepages and cc->nr_migratetypes this function
444	* does not modify any cc's fields, in particular it does not modify
445	* (or read for that matter) cc->migrate_pfn.
446	*/
447	unsigned long
448	isolate_migratepages_range(struct zone zone, struct compact_control cc,
449	unsigned long low_pfn, unsigned long end_pfn, bool unevictable)
450	{
451	unsigned long last_pageblock_nr = 0, pageblock_nr;
452	unsigned long nr_scanned = 0, nr_isolated = 0;
453	struct list_head *migratelist = &cc->migratepages;
454	isolate_mode_t mode = 0;
455	struct lruvec *lruvec;
456	unsigned long flags;
457	bool locked = false;
458	struct page page = NULL, valid_page = NULL;
459
460	/*
461	* Ensure that there are not too many pages isolated from the LRU
462	* list by either parallel reclaimers or compaction. If there are,
463	* delay for some time until fewer pages are isolated
464	*/
465	while (unlikely(too_many_isolated(zone))) {
466	/* async migration should just abort */
467	if (!cc->sync)
468	return 0;
469
470	congestion_wait(BLK_RW_ASYNC, HZ/10);
471
472	if (fatal_signal_pending(current))
473	return 0;
474	}
475
476	/* Time to isolate some pages for migration */
477	cond_resched();
478	for (; low_pfn < end_pfn; low_pfn++) {
479	/* give a chance to irqs before checking need_resched() */
480	if (locked && !((low_pfn+1) % SWAP_CLUSTER_MAX)) {
481	if (should_release_lock(&zone->lru_lock)) {
482	spin_unlock_irqrestore(&zone->lru_lock, flags);
483	locked = false;
484	}
485	}
486
487	/*
488	* migrate_pfn does not necessarily start aligned to a
489	* pageblock. Ensure that pfn_valid is called when moving
490	* into a new MAX_ORDER_NR_PAGES range in case of large
491	* memory holes within the zone
492	*/
493	if ((low_pfn & (MAX_ORDER_NR_PAGES - 1)) == 0) {
494	if (!pfn_valid(low_pfn)) {
495	low_pfn += MAX_ORDER_NR_PAGES - 1;
496	continue;
497	}
498	}
499
500	if (!pfn_valid_within(low_pfn))
501	continue;
502	nr_scanned++;
503
504	/*
505	* Get the page and ensure the page is within the same zone.
506	* See the comment in isolate_freepages about overlapping
507	* nodes. It is deliberate that the new zone lock is not taken
508	* as memory compaction should not move pages between nodes.
509	*/
510	page = pfn_to_page(low_pfn);
511	if (page_zone(page) != zone)
512	continue;
513
514	if (!valid_page)
515	valid_page = page;
516
517	/* If isolation recently failed, do not retry */
518	pageblock_nr = low_pfn >> pageblock_order;
519	if (!isolation_suitable(cc, page))
520	goto next_pageblock;
521
522	/* Skip if free */
523	if (PageBuddy(page))
524	continue;
525
526	/*
527	* For async migration, also only scan in MOVABLE blocks. Async
528	* migration is optimistic to see if the minimum amount of work
529	* satisfies the allocation
530	*/
531	if (!cc->sync && last_pageblock_nr != pageblock_nr &&
532	!migrate_async_suitable(get_pageblock_migratetype(page))) {
533	cc->finished_update_migrate = true;
534	goto next_pageblock;
535	}
536
537	/*
538	* Check may be lockless but that's ok as we recheck later.
539	* It's possible to migrate LRU pages and balloon pages
540	* Skip any other type of page
541	*/
542	if (!PageLRU(page)) {
543	if (unlikely(balloon_page_movable(page))) {
544	if (locked && balloon_page_isolate(page)) {
545	/* Successfully isolated */
546	cc->finished_update_migrate = true;
547	list_add(&page->lru, migratelist);
548	cc->nr_migratepages++;
549	nr_isolated++;
550	goto check_compact_cluster;
551	}
552	}
553	continue;
554	}
555
556	/*
557	* PageLRU is set. lru_lock normally excludes isolation
558	* splitting and collapsing (collapsing has already happened
559	* if PageLRU is set) but the lock is not necessarily taken
560	* here and it is wasteful to take it just to check transhuge.
561	* Check TransHuge without lock and skip the whole pageblock if
562	* it's either a transhuge or hugetlbfs page, as calling
563	* compound_order() without preventing THP from splitting the
564	* page underneath us may return surprising results.
565	*/
566	if (PageTransHuge(page)) {
567	if (!locked)
568	goto next_pageblock;
569	low_pfn += (1 << compound_order(page)) - 1;
570	continue;
571	}
572
573	/* Check if it is ok to still hold the lock */
574	locked = compact_checklock_irqsave(&zone->lru_lock, &flags,
575	locked, cc);
576	if (!locked \|\| fatal_signal_pending(current))
577	break;
578
579	/* Recheck PageLRU and PageTransHuge under lock */
580	if (!PageLRU(page))
581	continue;
582	if (PageTransHuge(page)) {
583	low_pfn += (1 << compound_order(page)) - 1;
584	continue;
585	}
586
587	if (!cc->sync)
588	mode \|= ISOLATE_ASYNC_MIGRATE;
589
590	if (unevictable)
591	mode \|= ISOLATE_UNEVICTABLE;
592
593	lruvec = mem_cgroup_page_lruvec(page, zone);
594
595	/* Try isolate the page */
596	if (__isolate_lru_page(page, mode) != 0)
597	continue;
598
599	VM_BUG_ON(PageTransCompound(page));
600
601	/* Successfully isolated */
602	cc->finished_update_migrate = true;
603	del_page_from_lru_list(page, lruvec, page_lru(page));
604	list_add(&page->lru, migratelist);
605	cc->nr_migratepages++;
606	nr_isolated++;
607
608	check_compact_cluster:
609	/* Avoid isolating too much */
610	if (cc->nr_migratepages == COMPACT_CLUSTER_MAX) {
611	++low_pfn;
612	break;
613	}
614
615	continue;
616
617	next_pageblock:
618	low_pfn = ALIGN(low_pfn + 1, pageblock_nr_pages) - 1;
619	last_pageblock_nr = pageblock_nr;
620	}
621
622	acct_isolated(zone, locked, cc);
623
624	if (locked)
625	spin_unlock_irqrestore(&zone->lru_lock, flags);
626
627	/* Update the pageblock-skip if the whole pageblock was scanned */
628	if (low_pfn == end_pfn)
629	update_pageblock_skip(cc, valid_page, nr_isolated, true);
630
631	trace_mm_compaction_isolate_migratepages(nr_scanned, nr_isolated);
632
633	count_compact_events(COMPACTMIGRATE_SCANNED, nr_scanned);
634	if (nr_isolated)
635	count_compact_events(COMPACTISOLATED, nr_isolated);
636
637	return low_pfn;
638	}
639
640	#endif /* CONFIG_COMPACTION \|\| CONFIG_CMA */
641	#ifdef CONFIG_COMPACTION
642	/*
643	* Based on information in the current compact_control, find blocks
644	* suitable for isolating free pages from and then isolate them.
645	*/
646	static void isolate_freepages(struct zone *zone,
647	struct compact_control *cc)
648	{
649	struct page *page;
650	unsigned long high_pfn, low_pfn, pfn, z_end_pfn, end_pfn;
651	int nr_freepages = cc->nr_freepages;
652	struct list_head *freelist = &cc->freepages;
653
654	/*
655	* Initialise the free scanner. The starting point is where we last
656	* scanned from (or the end of the zone if starting). The low point
657	* is the end of the pageblock the migration scanner is using.
658	*/
659	pfn = cc->free_pfn;
660	low_pfn = cc->migrate_pfn + pageblock_nr_pages;
661
662	/*
663	* Take care that if the migration scanner is at the end of the zone
664	* that the free scanner does not accidentally move to the next zone
665	* in the next isolation cycle.
666	*/
667	high_pfn = min(low_pfn, pfn);
668
669	z_end_pfn = zone_end_pfn(zone);
670
671	/*
672	* Isolate free pages until enough are available to migrate the
673	* pages on cc->migratepages. We stop searching if the migrate
674	* and free page scanners meet or enough free pages are isolated.
675	*/
676	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
677	pfn -= pageblock_nr_pages) {
678	unsigned long isolated;
679
680	/*
681	* This can iterate a massively long zone without finding any
682	* suitable migration targets, so periodically check if we need
683	* to schedule.
684	*/
685	cond_resched();
686
687	if (!pfn_valid(pfn))
688	continue;
689
690	/*
691	* Check for overlapping nodes/zones. It's possible on some
692	* configurations to have a setup like
693	* node0 node1 node0
694	* i.e. it's possible that all pages within a zones range of
695	* pages do not belong to a single zone.
696	*/
697	page = pfn_to_page(pfn);
698	if (page_zone(page) != zone)
699	continue;
700
701	/* Check the block is suitable for migration */
702	if (!suitable_migration_target(page))
703	continue;
704
705	/* If isolation recently failed, do not retry */
706	if (!isolation_suitable(cc, page))
707	continue;
708
709	/* Found a block suitable for isolating free pages from */
710	isolated = 0;
711
712	/*
713	* As pfn may not start aligned, pfn+pageblock_nr_page
714	* may cross a MAX_ORDER_NR_PAGES boundary and miss
715	* a pfn_valid check. Ensure isolate_freepages_block()
716	* only scans within a pageblock
717	*/
718	end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
719	end_pfn = min(end_pfn, z_end_pfn);
720	isolated = isolate_freepages_block(cc, pfn, end_pfn,
721	freelist, false);
722	nr_freepages += isolated;
723
724	/*
725	* Record the highest PFN we isolated pages from. When next
726	* looking for free pages, the search will restart here as
727	* page migration may have returned some pages to the allocator
728	*/
729	if (isolated) {
730	cc->finished_update_free = true;
731	high_pfn = max(high_pfn, pfn);
732	}
733	}
734
735	/* split_free_page does not map the pages */
736	map_pages(freelist);
737
738	cc->free_pfn = high_pfn;
739	cc->nr_freepages = nr_freepages;
740	}
741
742	/*
743	* This is a migrate-callback that "allocates" freepages by taking pages
744	* from the isolated freelists in the block we are migrating to.
745	*/
746	static struct page compaction_alloc(struct page migratepage,
747	unsigned long data,
748	int **result)
749	{
750	struct compact_control cc = (struct compact_control )data;
751	struct page *freepage;
752
753	/* Isolate free pages if necessary */
754	if (list_empty(&cc->freepages)) {
755	isolate_freepages(cc->zone, cc);
756
757	if (list_empty(&cc->freepages))
758	return NULL;
759	}
760
761	freepage = list_entry(cc->freepages.next, struct page, lru);
762	list_del(&freepage->lru);
763	cc->nr_freepages--;
764
765	return freepage;
766	}
767
768	/*
769	* We cannot control nr_migratepages and nr_freepages fully when migration is
770	* running as migrate_pages() has no knowledge of compact_control. When
771	* migration is complete, we count the number of pages on the lists by hand.
772	*/
773	static void update_nr_listpages(struct compact_control *cc)
774	{
775	int nr_migratepages = 0;
776	int nr_freepages = 0;
777	struct page *page;
778
779	list_for_each_entry(page, &cc->migratepages, lru)
780	nr_migratepages++;
781	list_for_each_entry(page, &cc->freepages, lru)
782	nr_freepages++;
783
784	cc->nr_migratepages = nr_migratepages;
785	cc->nr_freepages = nr_freepages;
786	}
787
788	/* possible outcome of isolate_migratepages */
789	typedef enum {
790	ISOLATE_ABORT, /* Abort compaction now */
791	ISOLATE_NONE, /* No pages isolated, continue scanning */
792	ISOLATE_SUCCESS, /* Pages isolated, migrate */
793	} isolate_migrate_t;
794
795	/*
796	* Isolate all pages that can be migrated from the block pointed to by
797	* the migrate scanner within compact_control.
798	*/
799	static isolate_migrate_t isolate_migratepages(struct zone *zone,
800	struct compact_control *cc)
801	{
802	unsigned long low_pfn, end_pfn;
803
804	/* Do not scan outside zone boundaries */
805	low_pfn = max(cc->migrate_pfn, zone->zone_start_pfn);
806
807	/* Only scan within a pageblock boundary */
808	end_pfn = ALIGN(low_pfn + 1, pageblock_nr_pages);
809
810	/* Do not cross the free scanner or scan within a memory hole */
811	if (end_pfn > cc->free_pfn \|\| !pfn_valid(low_pfn)) {
812	cc->migrate_pfn = end_pfn;
813	return ISOLATE_NONE;
814	}
815
816	/* Perform the isolation */
817	low_pfn = isolate_migratepages_range(zone, cc, low_pfn, end_pfn, false);
818	if (!low_pfn \|\| cc->contended)
819	return ISOLATE_ABORT;
820
821	cc->migrate_pfn = low_pfn;
822
823	return ISOLATE_SUCCESS;
824	}
825
826	static int compact_finished(struct zone *zone,
827	struct compact_control *cc)
828	{
829	unsigned int order;
830	unsigned long watermark;
831
832	if (fatal_signal_pending(current))
833	return COMPACT_PARTIAL;
834
835	/* Compaction run completes if the migrate and free scanner meet */
836	if (cc->free_pfn <= cc->migrate_pfn) {
837	/*
838	* Mark that the PG_migrate_skip information should be cleared
839	* by kswapd when it goes to sleep. kswapd does not set the
840	* flag itself as the decision to be clear should be directly
841	* based on an allocation request.
842	*/
843	if (!current_is_kswapd())
844	zone->compact_blockskip_flush = true;
845
846	return COMPACT_COMPLETE;
847	}
848
849	/*
850	* order == -1 is expected when compacting via
851	* /proc/sys/vm/compact_memory
852	*/
853	if (cc->order == -1)
854	return COMPACT_CONTINUE;
855
856	/* Compaction run is not finished if the watermark is not met */
857	watermark = low_wmark_pages(zone);
858	watermark += (1 << cc->order);
859
860	if (!zone_watermark_ok(zone, cc->order, watermark, 0, 0))
861	return COMPACT_CONTINUE;
862
863	/* Direct compactor: Is a suitable page free? */
864	for (order = cc->order; order < MAX_ORDER; order++) {
865	struct free_area *area = &zone->free_area[order];
866
867	/* Job done if page is free of the right migratetype */
868	if (!list_empty(&area->free_list[cc->migratetype]))
869	return COMPACT_PARTIAL;
870
871	/* Job done if allocation would set block type */
872	if (cc->order >= pageblock_order && area->nr_free)
873	return COMPACT_PARTIAL;
874	}
875
876	return COMPACT_CONTINUE;
877	}
878
879	/*
880	* compaction_suitable: Is this suitable to run compaction on this zone now?
881	* Returns
882	* COMPACT_SKIPPED - If there are too few free pages for compaction
883	* COMPACT_PARTIAL - If the allocation would succeed without compaction
884	* COMPACT_CONTINUE - If compaction should run now
885	*/
886	unsigned long compaction_suitable(struct zone *zone, int order)
887	{
888	int fragindex;
889	unsigned long watermark;
890
891	/*
892	* order == -1 is expected when compacting via
893	* /proc/sys/vm/compact_memory
894	*/
895	if (order == -1)
896	return COMPACT_CONTINUE;
897
898	/*
899	* Watermarks for order-0 must be met for compaction. Note the 2UL.
900	* This is because during migration, copies of pages need to be
901	* allocated and for a short time, the footprint is higher
902	*/
903	watermark = low_wmark_pages(zone) + (2UL << order);
904	if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
905	return COMPACT_SKIPPED;
906
907	/*
908	* fragmentation index determines if allocation failures are due to
909	* low memory or external fragmentation
910	*
911	* index of -1000 implies allocations might succeed depending on
912	* watermarks
913	* index towards 0 implies failure is due to lack of memory
914	* index towards 1000 implies failure is due to fragmentation
915	*
916	* Only compact if a failure would be due to fragmentation.
917	*/
918	fragindex = fragmentation_index(zone, order);
919	if (fragindex >= 0 && fragindex <= sysctl_extfrag_threshold)
920	return COMPACT_SKIPPED;
921
922	if (fragindex == -1000 && zone_watermark_ok(zone, order, watermark,
923	0, 0))
924	return COMPACT_PARTIAL;
925
926	return COMPACT_CONTINUE;
927	}
928
929	static int compact_zone(struct zone zone, struct compact_control cc)
930	{
931	int ret;
932	unsigned long start_pfn = zone->zone_start_pfn;
933	unsigned long end_pfn = zone_end_pfn(zone);
934
935	ret = compaction_suitable(zone, cc->order);
936	switch (ret) {
937	case COMPACT_PARTIAL:
938	case COMPACT_SKIPPED:
939	/* Compaction is likely to fail */
940	return ret;
941	case COMPACT_CONTINUE:
942	/* Fall through to compaction */
943	;
944	}
945
946	/*
947	* Setup to move all movable pages to the end of the zone. Used cached
948	* information on where the scanners should start but check that it
949	* is initialised by ensuring the values are within zone boundaries.
950	*/
951	cc->migrate_pfn = zone->compact_cached_migrate_pfn;
952	cc->free_pfn = zone->compact_cached_free_pfn;
953	if (cc->free_pfn < start_pfn \|\| cc->free_pfn > end_pfn) {
954	cc->free_pfn = end_pfn & ~(pageblock_nr_pages-1);
955	zone->compact_cached_free_pfn = cc->free_pfn;
956	}
957	if (cc->migrate_pfn < start_pfn \|\| cc->migrate_pfn > end_pfn) {
958	cc->migrate_pfn = start_pfn;
959	zone->compact_cached_migrate_pfn = cc->migrate_pfn;
960	}
961
962	/*
963	* Clear pageblock skip if there were failures recently and compaction
964	* is about to be retried after being deferred. kswapd does not do
965	* this reset as it'll reset the cached information when going to sleep.
966	*/
967	if (compaction_restarting(zone, cc->order) && !current_is_kswapd())
968	__reset_isolation_suitable(zone);
969
970	migrate_prep_local();
971
972	while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
973	unsigned long nr_migrate, nr_remaining;
974	int err;
975
976	switch (isolate_migratepages(zone, cc)) {
977	case ISOLATE_ABORT:
978	ret = COMPACT_PARTIAL;
979	putback_movable_pages(&cc->migratepages);
980	cc->nr_migratepages = 0;
981	goto out;
982	case ISOLATE_NONE:
983	continue;
984	case ISOLATE_SUCCESS:
985	;
986	}
987
988	nr_migrate = cc->nr_migratepages;
989	err = migrate_pages(&cc->migratepages, compaction_alloc,
990	(unsigned long)cc,
991	cc->sync ? MIGRATE_SYNC_LIGHT : MIGRATE_ASYNC,
992	MR_COMPACTION);
993	update_nr_listpages(cc);
994	nr_remaining = cc->nr_migratepages;
995
996	trace_mm_compaction_migratepages(nr_migrate - nr_remaining,
997	nr_remaining);
998
999	/* Release isolated pages not migrated */
1000	if (err) {
1001	putback_movable_pages(&cc->migratepages);
1002	cc->nr_migratepages = 0;
1003	if (err == -ENOMEM) {
1004	ret = COMPACT_PARTIAL;
1005	goto out;
1006	}
1007	}
1008	}
1009
1010	out:
1011	/* Release free pages and check accounting */
1012	cc->nr_freepages -= release_freepages(&cc->freepages);
1013	VM_BUG_ON(cc->nr_freepages != 0);
1014
1015	return ret;
1016	}
1017
1018	static unsigned long compact_zone_order(struct zone *zone,
1019	int order, gfp_t gfp_mask,
1020	bool sync, bool *contended)
1021	{
1022	unsigned long ret;
1023	struct compact_control cc = {
1024	.nr_freepages = 0,
1025	.nr_migratepages = 0,
1026	.order = order,
1027	.migratetype = allocflags_to_migratetype(gfp_mask),
1028	.zone = zone,
1029	.sync = sync,
1030	};
1031	INIT_LIST_HEAD(&cc.freepages);
1032	INIT_LIST_HEAD(&cc.migratepages);
1033
1034	ret = compact_zone(zone, &cc);
1035
1036	VM_BUG_ON(!list_empty(&cc.freepages));
1037	VM_BUG_ON(!list_empty(&cc.migratepages));
1038
1039	*contended = cc.contended;
1040	return ret;
1041	}
1042
1043	int sysctl_extfrag_threshold = 500;
1044
1045	/**
1046	* try_to_compact_pages - Direct compact to satisfy a high-order allocation
1047	* @zonelist: The zonelist used for the current allocation
1048	* @order: The order of the current allocation
1049	* @gfp_mask: The GFP mask of the current allocation
1050	* @nodemask: The allowed nodes to allocate from
1051	* @sync: Whether migration is synchronous or not
1052	* @contended: Return value that is true if compaction was aborted due to lock contention
1053	* @page: Optionally capture a free page of the requested order during compaction
1054	*
1055	* This is the main entry point for direct page compaction.
1056	*/
1057	unsigned long try_to_compact_pages(struct zonelist *zonelist,
1058	int order, gfp_t gfp_mask, nodemask_t *nodemask,
1059	bool sync, bool *contended)
1060	{
1061	enum zone_type high_zoneidx = gfp_zone(gfp_mask);
1062	int may_enter_fs = gfp_mask & __GFP_FS;
1063	int may_perform_io = gfp_mask & __GFP_IO;
1064	struct zoneref *z;
1065	struct zone *zone;
1066	int rc = COMPACT_SKIPPED;
1067	int alloc_flags = 0;
1068
1069	/* Check if the GFP flags allow compaction */
1070	if (!order \|\| !may_enter_fs \|\| !may_perform_io)
1071	return rc;
1072
1073	count_compact_event(COMPACTSTALL);
1074
1075	#ifdef CONFIG_CMA
1076	if (allocflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)
1077	alloc_flags \|= ALLOC_CMA;
1078	#endif
1079	/* Compact each zone in the list */
1080	for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx,
1081	nodemask) {
1082	int status;
1083
1084	status = compact_zone_order(zone, order, gfp_mask, sync,
1085	contended);
1086	rc = max(status, rc);
1087
1088	/* If a normal allocation would succeed, stop compacting */
1089	if (zone_watermark_ok(zone, order, low_wmark_pages(zone), 0,
1090	alloc_flags))
1091	break;
1092	}
1093
1094	return rc;
1095	}
1096
1097
1098	/* Compact all zones within a node */
1099	static void __compact_pgdat(pg_data_t pgdat, struct compact_control cc)
1100	{
1101	int zoneid;
1102	struct zone *zone;
1103
1104	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
1105
1106	zone = &pgdat->node_zones[zoneid];
1107	if (!populated_zone(zone))
1108	continue;
1109
1110	cc->nr_freepages = 0;
1111	cc->nr_migratepages = 0;
1112	cc->zone = zone;
1113	INIT_LIST_HEAD(&cc->freepages);
1114	INIT_LIST_HEAD(&cc->migratepages);
1115
1116	if (cc->order == -1 \|\| !compaction_deferred(zone, cc->order))
1117	compact_zone(zone, cc);
1118
1119	if (cc->order > 0) {
1120	int ok = zone_watermark_ok(zone, cc->order,
1121	low_wmark_pages(zone), 0, 0);
1122	if (ok && cc->order >= zone->compact_order_failed)
1123	zone->compact_order_failed = cc->order + 1;
1124	/* Currently async compaction is never deferred. */
1125	else if (!ok && cc->sync)
1126	defer_compaction(zone, cc->order);
1127	}
1128
1129	VM_BUG_ON(!list_empty(&cc->freepages));
1130	VM_BUG_ON(!list_empty(&cc->migratepages));
1131	}
1132	}
1133
1134	void compact_pgdat(pg_data_t *pgdat, int order)
1135	{
1136	struct compact_control cc = {
1137	.order = order,
1138	.sync = false,
1139	};
1140
1141	if (!order)
1142	return;
1143
1144	__compact_pgdat(pgdat, &cc);
1145	}
1146
1147	static void compact_node(int nid)
1148	{
1149	struct compact_control cc = {
1150	.order = -1,
1151	.sync = true,
1152	};
1153
1154	__compact_pgdat(NODE_DATA(nid), &cc);
1155	}
1156
1157	/* Compact all nodes in the system */
1158	static void compact_nodes(void)
1159	{
1160	int nid;
1161
1162	/* Flush pending updates to the LRU lists */
1163	lru_add_drain_all();
1164
1165	for_each_online_node(nid)
1166	compact_node(nid);
1167	}
1168
1169	/* The written value is actually unused, all memory is compacted */
1170	int sysctl_compact_memory;
1171
1172	/* This is the entry point for compacting all nodes via /proc/sys/vm */
1173	int sysctl_compaction_handler(struct ctl_table *table, int write,
1174	void __user buffer, size_t length, loff_t *ppos)
1175	{
1176	if (write)
1177	compact_nodes();
1178
1179	return 0;
1180	}
1181
1182	int sysctl_extfrag_handler(struct ctl_table *table, int write,
1183	void __user buffer, size_t length, loff_t *ppos)
1184	{
1185	proc_dointvec_minmax(table, write, buffer, length, ppos);
1186
1187	return 0;
1188	}
1189
1190	#if defined(CONFIG_SYSFS) && defined(CONFIG_NUMA)
1191	ssize_t sysfs_compact_node(struct device *dev,
1192	struct device_attribute *attr,
1193	const char *buf, size_t count)
1194	{
1195	int nid = dev->id;
1196
1197	if (nid >= 0 && nid < nr_node_ids && node_online(nid)) {
1198	/* Flush pending updates to the LRU lists */
1199	lru_add_drain_all();
1200
1201	compact_node(nid);
1202	}
1203
1204	return count;
1205	}
1206	static DEVICE_ATTR(compact, S_IWUSR, NULL, sysfs_compact_node);
1207
1208	int compaction_register_node(struct node *node)
1209	{
1210	return device_create_file(&node->dev, &dev_attr_compact);
1211	}
1212
1213	void compaction_unregister_node(struct node *node)
1214	{
1215	return device_remove_file(&node->dev, &dev_attr_compact);
1216	}
1217	#endif /* CONFIG_SYSFS && CONFIG_NUMA */
1218
1219	#endif /* CONFIG_COMPACTION */
1220

Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9

Kernel

Kernel Git Source Tree

Root/mm/compaction.c

interactive