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 "internal.h"
 18
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 19#define CREATE_TRACE_POINTS
 20#include <trace/events/compaction.h>
 21
 22/*
 23 * compact_control is used to track pages being migrated and the free pages
 24 * they are being migrated to during memory compaction. The free_pfn starts
 25 * at the end of a zone and migrate_pfn begins at the start. Movable pages
 26 * are moved to the end of a zone during a compaction run and the run
 27 * completes when free_pfn <= migrate_pfn
 28 */
 29struct compact_control {
 30	struct list_head freepages;	/* List of free pages to migrate to */
 31	struct list_head migratepages;	/* List of pages being migrated */
 32	unsigned long nr_freepages;	/* Number of isolated free pages */
 33	unsigned long nr_migratepages;	/* Number of pages to migrate */
 34	unsigned long free_pfn;		/* isolate_freepages search base */
 35	unsigned long migrate_pfn;	/* isolate_migratepages search base */
 36	bool sync;			/* Synchronous migration */
 37
 38	/* Account for isolated anon and file pages */
 39	unsigned long nr_anon;
 40	unsigned long nr_file;
 41
 42	unsigned int order;		/* order a direct compactor needs */
 43	int migratetype;		/* MOVABLE, RECLAIMABLE etc */
 44	struct zone *zone;
 45};
 
 
 
 
 
 
 
 
 46
 47static unsigned long release_freepages(struct list_head *freelist)
 48{
 49	struct page *page, *next;
 50	unsigned long count = 0;
 51
 52	list_for_each_entry_safe(page, next, freelist, lru) {
 
 53		list_del(&page->lru);
 54		__free_page(page);
 55		count++;
 
 56	}
 57
 58	return count;
 59}
 60
 61/* Isolate free pages onto a private freelist. Must hold zone->lock */
 62static unsigned long isolate_freepages_block(struct zone *zone,
 63				unsigned long blockpfn,
 64				struct list_head *freelist)
 65{
 66	unsigned long zone_end_pfn, end_pfn;
 67	int nr_scanned = 0, total_isolated = 0;
 68	struct page *cursor;
 69
 70	/* Get the last PFN we should scan for free pages at */
 71	zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages;
 72	end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn);
 73
 74	/* Find the first usable PFN in the block to initialse page cursor */
 75	for (; blockpfn < end_pfn; blockpfn++) {
 76		if (pfn_valid_within(blockpfn))
 77			break;
 78	}
 79	cursor = pfn_to_page(blockpfn);
 80
 81	/* Isolate free pages. This assumes the block is valid */
 82	for (; blockpfn < end_pfn; blockpfn++, cursor++) {
 83		int isolated, i;
 84		struct page *page = cursor;
 85
 86		if (!pfn_valid_within(blockpfn))
 87			continue;
 88		nr_scanned++;
 89
 90		if (!PageBuddy(page))
 91			continue;
 92
 93		/* Found a free page, break it into order-0 pages */
 94		isolated = split_free_page(page);
 95		total_isolated += isolated;
 96		for (i = 0; i < isolated; i++) {
 97			list_add(&page->lru, freelist);
 98			page++;
 99		}
 
100
101		/* If a page was split, advance to the end of it */
102		if (isolated) {
103			blockpfn += isolated - 1;
104			cursor += isolated - 1;
105		}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
106	}
107
108	trace_mm_compaction_isolate_freepages(nr_scanned, total_isolated);
109	return total_isolated;
 
110}
111
112/* Returns true if the page is within a block suitable for migration to */
113static bool suitable_migration_target(struct page *page)
 
 
 
 
 
114{
 
 
 
 
 
 
115
116	int migratetype = get_pageblock_migratetype(page);
 
117
118	/* Don't interfere with memory hot-remove or the min_free_kbytes blocks */
119	if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE)
 
 
120		return false;
121
122	/* If the page is a large free page, then allow migration */
123	if (PageBuddy(page) && page_order(page) >= pageblock_order)
124		return true;
125
126	/* If the block is MIGRATE_MOVABLE, allow migration */
127	if (migratetype == MIGRATE_MOVABLE)
 
 
 
128		return true;
129
130	/* Otherwise skip the block */
131	return false;
 
 
 
 
 
 
 
132}
133
134/*
135 * Based on information in the current compact_control, find blocks
136 * suitable for isolating free pages from and then isolate them.
 
137 */
138static void isolate_freepages(struct zone *zone,
139				struct compact_control *cc)
140{
141	struct page *page;
142	unsigned long high_pfn, low_pfn, pfn;
143	unsigned long flags;
144	int nr_freepages = cc->nr_freepages;
145	struct list_head *freelist = &cc->freepages;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
146
147	/*
148	 * Initialise the free scanner. The starting point is where we last
149	 * scanned from (or the end of the zone if starting). The low point
150	 * is the end of the pageblock the migration scanner is using.
151	 */
152	pfn = cc->free_pfn;
153	low_pfn = cc->migrate_pfn + pageblock_nr_pages;
154
155	/*
156	 * Take care that if the migration scanner is at the end of the zone
157	 * that the free scanner does not accidentally move to the next zone
158	 * in the next isolation cycle.
159	 */
160	high_pfn = min(low_pfn, pfn);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
161
162	/*
163	 * Isolate free pages until enough are available to migrate the
164	 * pages on cc->migratepages. We stop searching if the migrate
165	 * and free page scanners meet or enough free pages are isolated.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
166	 */
167	for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages;
168					pfn -= pageblock_nr_pages) {
169		unsigned long isolated;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
170
171		if (!pfn_valid(pfn))
 
 
172			continue;
173
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
174		/*
175		 * Check for overlapping nodes/zones. It's possible on some
176		 * configurations to have a setup like
177		 * node0 node1 node0
178		 * i.e. it's possible that all pages within a zones range of
179		 * pages do not belong to a single zone.
180		 */
181		page = pfn_to_page(pfn);
182		if (page_zone(page) != zone)
183			continue;
 
184
185		/* Check the block is suitable for migration */
186		if (!suitable_migration_target(page))
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
187			continue;
188
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
189		/*
190		 * Found a block suitable for isolating free pages from. Now
191		 * we disabled interrupts, double check things are ok and
192		 * isolate the pages. This is to minimise the time IRQs
193		 * are disabled
194		 */
195		isolated = 0;
196		spin_lock_irqsave(&zone->lock, flags);
197		if (suitable_migration_target(page)) {
198			isolated = isolate_freepages_block(zone, pfn, freelist);
199			nr_freepages += isolated;
200		}
201		spin_unlock_irqrestore(&zone->lock, flags);
 
 
 
 
 
 
202
203		/*
204		 * Record the highest PFN we isolated pages from. When next
205		 * looking for free pages, the search will restart here as
206		 * page migration may have returned some pages to the allocator
207		 */
208		if (isolated)
209			high_pfn = max(high_pfn, pfn);
210	}
211
212	/* split_free_page does not map the pages */
213	list_for_each_entry(page, freelist, lru) {
214		arch_alloc_page(page, 0);
215		kernel_map_pages(page, 1, 1);
 
216	}
217
218	cc->free_pfn = high_pfn;
219	cc->nr_freepages = nr_freepages;
220}
221
222/* Update the number of anon and file isolated pages in the zone */
223static void acct_isolated(struct zone *zone, struct compact_control *cc)
224{
225	struct page *page;
226	unsigned int count[NR_LRU_LISTS] = { 0, };
227
228	list_for_each_entry(page, &cc->migratepages, lru) {
229		int lru = page_lru_base_type(page);
230		count[lru]++;
 
231	}
232
233	cc->nr_anon = count[LRU_ACTIVE_ANON] + count[LRU_INACTIVE_ANON];
234	cc->nr_file = count[LRU_ACTIVE_FILE] + count[LRU_INACTIVE_FILE];
235	__mod_zone_page_state(zone, NR_ISOLATED_ANON, cc->nr_anon);
236	__mod_zone_page_state(zone, NR_ISOLATED_FILE, cc->nr_file);
237}
238
239/* Similar to reclaim, but different enough that they don't share logic */
240static bool too_many_isolated(struct zone *zone)
241{
 
 
242	unsigned long active, inactive, isolated;
243
244	inactive = zone_page_state(zone, NR_INACTIVE_FILE) +
245					zone_page_state(zone, NR_INACTIVE_ANON);
246	active = zone_page_state(zone, NR_ACTIVE_FILE) +
247					zone_page_state(zone, NR_ACTIVE_ANON);
248	isolated = zone_page_state(zone, NR_ISOLATED_FILE) +
249					zone_page_state(zone, NR_ISOLATED_ANON);
 
 
 
 
250
251	return isolated > (inactive + active) / 2;
252}
253
254/* possible outcome of isolate_migratepages */
255typedef enum {
256	ISOLATE_ABORT,		/* Abort compaction now */
257	ISOLATE_NONE,		/* No pages isolated, continue scanning */
258	ISOLATE_SUCCESS,	/* Pages isolated, migrate */
259} isolate_migrate_t;
260
261/*
262 * Isolate all pages that can be migrated from the block pointed to by
263 * the migrate scanner within compact_control.
 
 
 
 
 
 
264 */
265static isolate_migrate_t isolate_migratepages(struct zone *zone,
266					struct compact_control *cc)
 
267{
268	unsigned long low_pfn, end_pfn;
269	unsigned long last_pageblock_nr = 0, pageblock_nr;
270	unsigned long nr_scanned = 0, nr_isolated = 0;
271	struct list_head *migratelist = &cc->migratepages;
272
273	/* Do not scan outside zone boundaries */
274	low_pfn = max(cc->migrate_pfn, zone->zone_start_pfn);
 
 
 
 
 
 
275
276	/* Only scan within a pageblock boundary */
277	end_pfn = ALIGN(low_pfn + pageblock_nr_pages, pageblock_nr_pages);
278
279	/* Do not cross the free scanner or scan within a memory hole */
280	if (end_pfn > cc->free_pfn || !pfn_valid(low_pfn)) {
281		cc->migrate_pfn = end_pfn;
282		return ISOLATE_NONE;
283	}
284
285	/*
286	 * Ensure that there are not too many pages isolated from the LRU
287	 * list by either parallel reclaimers or compaction. If there are,
288	 * delay for some time until fewer pages are isolated
289	 */
290	while (unlikely(too_many_isolated(zone))) {
 
 
 
 
291		/* async migration should just abort */
292		if (!cc->sync)
293			return ISOLATE_ABORT;
294
295		congestion_wait(BLK_RW_ASYNC, HZ/10);
296
297		if (fatal_signal_pending(current))
298			return ISOLATE_ABORT;
299	}
300
301	/* Time to isolate some pages for migration */
302	cond_resched();
303	spin_lock_irq(&zone->lru_lock);
 
 
 
 
 
 
304	for (; low_pfn < end_pfn; low_pfn++) {
305		struct page *page;
306		bool locked = true;
307
308		/* give a chance to irqs before checking need_resched() */
309		if (!((low_pfn+1) % SWAP_CLUSTER_MAX)) {
310			spin_unlock_irq(&zone->lru_lock);
311			locked = false;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
312		}
313		if (need_resched() || spin_is_contended(&zone->lru_lock)) {
314			if (locked)
315				spin_unlock_irq(&zone->lru_lock);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
316			cond_resched();
317			spin_lock_irq(&zone->lru_lock);
318			if (fatal_signal_pending(current))
319				break;
320		} else if (!locked)
321			spin_lock_irq(&zone->lru_lock);
322
323		if (!pfn_valid_within(low_pfn))
324			continue;
325		nr_scanned++;
326
327		/* Get the page and skip if free */
328		page = pfn_to_page(low_pfn);
329		if (PageBuddy(page))
330			continue;
331
332		/*
333		 * For async migration, also only scan in MOVABLE blocks. Async
334		 * migration is optimistic to see if the minimum amount of work
335		 * satisfies the allocation
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
336		 */
337		pageblock_nr = low_pfn >> pageblock_order;
338		if (!cc->sync && last_pageblock_nr != pageblock_nr &&
339				get_pageblock_migratetype(page) != MIGRATE_MOVABLE) {
340			low_pfn += pageblock_nr_pages;
341			low_pfn = ALIGN(low_pfn, pageblock_nr_pages) - 1;
342			last_pageblock_nr = pageblock_nr;
 
 
 
 
343			continue;
344		}
345
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
346		if (!PageLRU(page))
347			continue;
 
 
 
 
348
349		/*
350		 * PageLRU is set, and lru_lock excludes isolation,
351		 * splitting and collapsing (collapsing has already
352		 * happened if PageLRU is set).
 
353		 */
354		if (PageTransHuge(page)) {
355			low_pfn += (1 << compound_order(page)) - 1;
356			continue;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
357		}
358
359		/* Try isolate the page */
360		if (__isolate_lru_page(page, ISOLATE_BOTH, 0) != 0)
361			continue;
362
363		VM_BUG_ON(PageTransCompound(page));
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
364
365		/* Successfully isolated */
366		del_page_from_lru_list(zone, page, page_lru(page));
367		list_add(&page->lru, migratelist);
368		cc->nr_migratepages++;
369		nr_isolated++;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
370
371		/* Avoid isolating too much */
372		if (cc->nr_migratepages == COMPACT_CLUSTER_MAX)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
373			break;
374	}
375
376	acct_isolated(zone, cc);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
377
378	spin_unlock_irq(&zone->lru_lock);
379	cc->migrate_pfn = low_pfn;
380
381	trace_mm_compaction_isolate_migratepages(nr_scanned, nr_isolated);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
382
383	return ISOLATE_SUCCESS;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
384}
385
386/*
387 * This is a migrate-callback that "allocates" freepages by taking pages
388 * from the isolated freelists in the block we are migrating to.
389 */
390static struct page *compaction_alloc(struct page *migratepage,
391					unsigned long data,
392					int **result)
393{
394	struct compact_control *cc = (struct compact_control *)data;
395	struct page *freepage;
396
397	/* Isolate free pages if necessary */
398	if (list_empty(&cc->freepages)) {
399		isolate_freepages(cc->zone, cc);
400
401		if (list_empty(&cc->freepages))
402			return NULL;
403	}
404
405	freepage = list_entry(cc->freepages.next, struct page, lru);
406	list_del(&freepage->lru);
407	cc->nr_freepages--;
408
409	return freepage;
410}
411
412/*
413 * We cannot control nr_migratepages and nr_freepages fully when migration is
414 * running as migrate_pages() has no knowledge of compact_control. When
415 * migration is complete, we count the number of pages on the lists by hand.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
416 */
417static void update_nr_listpages(struct compact_control *cc)
418{
419	int nr_migratepages = 0;
420	int nr_freepages = 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
421	struct page *page;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
422
423	list_for_each_entry(page, &cc->migratepages, lru)
424		nr_migratepages++;
425	list_for_each_entry(page, &cc->freepages, lru)
426		nr_freepages++;
 
 
 
427
428	cc->nr_migratepages = nr_migratepages;
429	cc->nr_freepages = nr_freepages;
430}
431
432static int compact_finished(struct zone *zone,
433			    struct compact_control *cc)
 
 
 
434{
435	unsigned int order;
436	unsigned long watermark;
437
438	if (fatal_signal_pending(current))
439		return COMPACT_PARTIAL;
 
 
 
 
 
 
 
440
441	/* Compaction run completes if the migrate and free scanner meet */
442	if (cc->free_pfn <= cc->migrate_pfn)
443		return COMPACT_COMPLETE;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
444
445	/*
446	 * order == -1 is expected when compacting via
447	 * /proc/sys/vm/compact_memory
 
448	 */
449	if (cc->order == -1)
450		return COMPACT_CONTINUE;
 
 
 
 
 
 
 
 
 
 
 
 
451
452	/* Compaction run is not finished if the watermark is not met */
453	watermark = low_wmark_pages(zone);
454	watermark += (1 << cc->order);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
455
456	if (!zone_watermark_ok(zone, cc->order, watermark, 0, 0))
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
457		return COMPACT_CONTINUE;
458
459	/* Direct compactor: Is a suitable page free? */
 
460	for (order = cc->order; order < MAX_ORDER; order++) {
 
 
 
461		/* Job done if page is free of the right migratetype */
462		if (!list_empty(&zone->free_area[order].free_list[cc->migratetype]))
463			return COMPACT_PARTIAL;
464
465		/* Job done if allocation would set block type */
466		if (order >= pageblock_order && zone->free_area[order].nr_free)
467			return COMPACT_PARTIAL;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
468	}
469
470	return COMPACT_CONTINUE;
 
 
 
 
471}
472
473/*
474 * compaction_suitable: Is this suitable to run compaction on this zone now?
475 * Returns
476 *   COMPACT_SKIPPED  - If there are too few free pages for compaction
477 *   COMPACT_PARTIAL  - If the allocation would succeed without compaction
478 *   COMPACT_CONTINUE - If compaction should run now
479 */
480unsigned long compaction_suitable(struct zone *zone, int order)
 
 
 
 
 
 
 
 
481{
482	int fragindex;
483	unsigned long watermark;
484
 
 
 
 
485	/*
486	 * order == -1 is expected when compacting via
487	 * /proc/sys/vm/compact_memory
488	 */
489	if (order == -1)
490		return COMPACT_CONTINUE;
 
491
492	/*
493	 * Watermarks for order-0 must be met for compaction. Note the 2UL.
494	 * This is because during migration, copies of pages need to be
495	 * allocated and for a short time, the footprint is higher
 
 
 
 
 
 
 
 
 
496	 */
497	watermark = low_wmark_pages(zone) + (2UL << order);
498	if (!zone_watermark_ok(zone, 0, watermark, 0, 0))
 
 
 
499		return COMPACT_SKIPPED;
500
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
501	/*
502	 * fragmentation index determines if allocation failures are due to
503	 * low memory or external fragmentation
504	 *
505	 * index of -1000 implies allocations might succeed depending on
506	 * watermarks
507	 * index towards 0 implies failure is due to lack of memory
508	 * index towards 1000 implies failure is due to fragmentation
509	 *
510	 * Only compact if a failure would be due to fragmentation.
 
 
 
 
 
511	 */
512	fragindex = fragmentation_index(zone, order);
513	if (fragindex >= 0 && fragindex <= sysctl_extfrag_threshold)
514		return COMPACT_SKIPPED;
 
 
515
516	if (fragindex == -1000 && zone_watermark_ok(zone, order, watermark,
517	    0, 0))
518		return COMPACT_PARTIAL;
519
520	return COMPACT_CONTINUE;
521}
522
523static int compact_zone(struct zone *zone, struct compact_control *cc)
 
524{
525	int ret;
 
526
527	ret = compaction_suitable(zone, cc->order);
528	switch (ret) {
529	case COMPACT_PARTIAL:
530	case COMPACT_SKIPPED:
531		/* Compaction is likely to fail */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
532		return ret;
533	case COMPACT_CONTINUE:
534		/* Fall through to compaction */
535		;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
536	}
537
538	/* Setup to move all movable pages to the end of the zone */
539	cc->migrate_pfn = zone->zone_start_pfn;
540	cc->free_pfn = cc->migrate_pfn + zone->spanned_pages;
541	cc->free_pfn &= ~(pageblock_nr_pages-1);
542
543	migrate_prep_local();
 
 
 
 
 
 
 
 
 
 
 
544
545	while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) {
546		unsigned long nr_migrate, nr_remaining;
 
 
547		int err;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
548
549		switch (isolate_migratepages(zone, cc)) {
550		case ISOLATE_ABORT:
551			ret = COMPACT_PARTIAL;
 
 
552			goto out;
553		case ISOLATE_NONE:
554			continue;
 
 
 
 
 
 
 
 
 
 
555		case ISOLATE_SUCCESS:
556			;
 
557		}
558
559		nr_migrate = cc->nr_migratepages;
560		err = migrate_pages(&cc->migratepages, compaction_alloc,
561				(unsigned long)cc, false,
562				cc->sync);
563		update_nr_listpages(cc);
564		nr_remaining = cc->nr_migratepages;
565
566		count_vm_event(COMPACTBLOCKS);
567		count_vm_events(COMPACTPAGES, nr_migrate - nr_remaining);
568		if (nr_remaining)
569			count_vm_events(COMPACTPAGEFAILED, nr_remaining);
570		trace_mm_compaction_migratepages(nr_migrate - nr_remaining,
571						nr_remaining);
572
573		/* Release LRU pages not migrated */
 
 
 
574		if (err) {
575			putback_lru_pages(&cc->migratepages);
576			cc->nr_migratepages = 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
577		}
578
 
 
 
 
 
579	}
580
581out:
582	/* Release free pages and check accounting */
583	cc->nr_freepages -= release_freepages(&cc->freepages);
584	VM_BUG_ON(cc->nr_freepages != 0);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
585
586	return ret;
587}
588
589unsigned long compact_zone_order(struct zone *zone,
590				 int order, gfp_t gfp_mask,
591				 bool sync)
 
592{
 
593	struct compact_control cc = {
594		.nr_freepages = 0,
595		.nr_migratepages = 0,
596		.order = order,
597		.migratetype = allocflags_to_migratetype(gfp_mask),
 
598		.zone = zone,
599		.sync = sync,
 
 
 
 
 
 
 
 
 
 
 
600	};
601	INIT_LIST_HEAD(&cc.freepages);
602	INIT_LIST_HEAD(&cc.migratepages);
603
604	return compact_zone(zone, &cc);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
605}
606
607int sysctl_extfrag_threshold = 500;
608
609/**
610 * try_to_compact_pages - Direct compact to satisfy a high-order allocation
611 * @zonelist: The zonelist used for the current allocation
612 * @order: The order of the current allocation
613 * @gfp_mask: The GFP mask of the current allocation
614 * @nodemask: The allowed nodes to allocate from
615 * @sync: Whether migration is synchronous or not
 
 
 
616 *
617 * This is the main entry point for direct page compaction.
618 */
619unsigned long try_to_compact_pages(struct zonelist *zonelist,
620			int order, gfp_t gfp_mask, nodemask_t *nodemask,
621			bool sync)
622{
623	enum zone_type high_zoneidx = gfp_zone(gfp_mask);
624	int may_enter_fs = gfp_mask & __GFP_FS;
625	int may_perform_io = gfp_mask & __GFP_IO;
626	struct zoneref *z;
627	struct zone *zone;
628	int rc = COMPACT_SKIPPED;
629
630	/*
631	 * Check whether it is worth even starting compaction. The order check is
632	 * made because an assumption is made that the page allocator can satisfy
633	 * the "cheaper" orders without taking special steps
634	 */
635	if (!order || !may_enter_fs || !may_perform_io)
636		return rc;
637
638	count_vm_event(COMPACTSTALL);
639
640	/* Compact each zone in the list */
641	for_each_zone_zonelist_nodemask(zone, z, zonelist, high_zoneidx,
642								nodemask) {
643		int status;
 
 
 
 
 
 
644
645		status = compact_zone_order(zone, order, gfp_mask, sync);
 
646		rc = max(status, rc);
647
648		/* If a normal allocation would succeed, stop compacting */
649		if (zone_watermark_ok(zone, order, low_wmark_pages(zone), 0, 0))
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
650			break;
651	}
652
653	return rc;
654}
655
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
656
657/* Compact all zones within a node */
658static int compact_node(int nid)
659{
 
660	int zoneid;
661	pg_data_t *pgdat;
662	struct zone *zone;
 
 
 
 
 
 
 
663
664	if (nid < 0 || nid >= nr_node_ids || !node_online(nid))
665		return -EINVAL;
666	pgdat = NODE_DATA(nid);
667
668	/* Flush pending updates to the LRU lists */
669	lru_add_drain_all();
670
671	for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) {
672		struct compact_control cc = {
673			.nr_freepages = 0,
674			.nr_migratepages = 0,
675			.order = -1,
676		};
677
678		zone = &pgdat->node_zones[zoneid];
679		if (!populated_zone(zone))
680			continue;
681
682		cc.zone = zone;
683		INIT_LIST_HEAD(&cc.freepages);
684		INIT_LIST_HEAD(&cc.migratepages);
685
686		compact_zone(zone, &cc);
687
688		VM_BUG_ON(!list_empty(&cc.freepages));
689		VM_BUG_ON(!list_empty(&cc.migratepages));
690	}
691
692	return 0;
693}
694
695/* Compact all nodes in the system */
696static int compact_nodes(void)
697{
698	int nid;
699
 
 
 
700	for_each_online_node(nid)
701		compact_node(nid);
702
703	return COMPACT_COMPLETE;
704}
705
706/* The written value is actually unused, all memory is compacted */
707int sysctl_compact_memory;
 
 
 
 
708
709/* This is the entry point for compacting all nodes via /proc/sys/vm */
710int sysctl_compaction_handler(struct ctl_table *table, int write,
711			void __user *buffer, size_t *length, loff_t *ppos)
712{
713	if (write)
714		return compact_nodes();
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
715
716	return 0;
717}
718
719int sysctl_extfrag_handler(struct ctl_table *table, int write,
720			void __user *buffer, size_t *length, loff_t *ppos)
 
 
 
 
721{
722	proc_dointvec_minmax(table, write, buffer, length, ppos);
 
723
724	return 0;
725}
726
727#if defined(CONFIG_SYSFS) && defined(CONFIG_NUMA)
728ssize_t sysfs_compact_node(struct sys_device *dev,
729			struct sysdev_attribute *attr,
730			const char *buf, size_t count)
731{
732	compact_node(dev->id);
 
 
 
 
 
 
 
733
734	return count;
735}
736static SYSDEV_ATTR(compact, S_IWUSR, NULL, sysfs_compact_node);
737
738int compaction_register_node(struct node *node)
739{
740	return sysdev_create_file(&node->sysdev, &attr_compact);
741}
742
743void compaction_unregister_node(struct node *node)
744{
745	return sysdev_remove_file(&node->sysdev, &attr_compact);
746}
747#endif /* CONFIG_SYSFS && CONFIG_NUMA */