Commit | Line | Data |
---|---|---|
748446bb MG |
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> | |
76ab0f53 | 15 | #include <linux/sysctl.h> |
748446bb MG |
16 | #include "internal.h" |
17 | ||
18 | /* | |
19 | * compact_control is used to track pages being migrated and the free pages | |
20 | * they are being migrated to during memory compaction. The free_pfn starts | |
21 | * at the end of a zone and migrate_pfn begins at the start. Movable pages | |
22 | * are moved to the end of a zone during a compaction run and the run | |
23 | * completes when free_pfn <= migrate_pfn | |
24 | */ | |
25 | struct compact_control { | |
26 | struct list_head freepages; /* List of free pages to migrate to */ | |
27 | struct list_head migratepages; /* List of pages being migrated */ | |
28 | unsigned long nr_freepages; /* Number of isolated free pages */ | |
29 | unsigned long nr_migratepages; /* Number of pages to migrate */ | |
30 | unsigned long free_pfn; /* isolate_freepages search base */ | |
31 | unsigned long migrate_pfn; /* isolate_migratepages search base */ | |
32 | ||
33 | /* Account for isolated anon and file pages */ | |
34 | unsigned long nr_anon; | |
35 | unsigned long nr_file; | |
36 | ||
37 | struct zone *zone; | |
38 | }; | |
39 | ||
40 | static unsigned long release_freepages(struct list_head *freelist) | |
41 | { | |
42 | struct page *page, *next; | |
43 | unsigned long count = 0; | |
44 | ||
45 | list_for_each_entry_safe(page, next, freelist, lru) { | |
46 | list_del(&page->lru); | |
47 | __free_page(page); | |
48 | count++; | |
49 | } | |
50 | ||
51 | return count; | |
52 | } | |
53 | ||
54 | /* Isolate free pages onto a private freelist. Must hold zone->lock */ | |
55 | static unsigned long isolate_freepages_block(struct zone *zone, | |
56 | unsigned long blockpfn, | |
57 | struct list_head *freelist) | |
58 | { | |
59 | unsigned long zone_end_pfn, end_pfn; | |
60 | int total_isolated = 0; | |
61 | struct page *cursor; | |
62 | ||
63 | /* Get the last PFN we should scan for free pages at */ | |
64 | zone_end_pfn = zone->zone_start_pfn + zone->spanned_pages; | |
65 | end_pfn = min(blockpfn + pageblock_nr_pages, zone_end_pfn); | |
66 | ||
67 | /* Find the first usable PFN in the block to initialse page cursor */ | |
68 | for (; blockpfn < end_pfn; blockpfn++) { | |
69 | if (pfn_valid_within(blockpfn)) | |
70 | break; | |
71 | } | |
72 | cursor = pfn_to_page(blockpfn); | |
73 | ||
74 | /* Isolate free pages. This assumes the block is valid */ | |
75 | for (; blockpfn < end_pfn; blockpfn++, cursor++) { | |
76 | int isolated, i; | |
77 | struct page *page = cursor; | |
78 | ||
79 | if (!pfn_valid_within(blockpfn)) | |
80 | continue; | |
81 | ||
82 | if (!PageBuddy(page)) | |
83 | continue; | |
84 | ||
85 | /* Found a free page, break it into order-0 pages */ | |
86 | isolated = split_free_page(page); | |
87 | total_isolated += isolated; | |
88 | for (i = 0; i < isolated; i++) { | |
89 | list_add(&page->lru, freelist); | |
90 | page++; | |
91 | } | |
92 | ||
93 | /* If a page was split, advance to the end of it */ | |
94 | if (isolated) { | |
95 | blockpfn += isolated - 1; | |
96 | cursor += isolated - 1; | |
97 | } | |
98 | } | |
99 | ||
100 | return total_isolated; | |
101 | } | |
102 | ||
103 | /* Returns true if the page is within a block suitable for migration to */ | |
104 | static bool suitable_migration_target(struct page *page) | |
105 | { | |
106 | ||
107 | int migratetype = get_pageblock_migratetype(page); | |
108 | ||
109 | /* Don't interfere with memory hot-remove or the min_free_kbytes blocks */ | |
110 | if (migratetype == MIGRATE_ISOLATE || migratetype == MIGRATE_RESERVE) | |
111 | return false; | |
112 | ||
113 | /* If the page is a large free page, then allow migration */ | |
114 | if (PageBuddy(page) && page_order(page) >= pageblock_order) | |
115 | return true; | |
116 | ||
117 | /* If the block is MIGRATE_MOVABLE, allow migration */ | |
118 | if (migratetype == MIGRATE_MOVABLE) | |
119 | return true; | |
120 | ||
121 | /* Otherwise skip the block */ | |
122 | return false; | |
123 | } | |
124 | ||
125 | /* | |
126 | * Based on information in the current compact_control, find blocks | |
127 | * suitable for isolating free pages from and then isolate them. | |
128 | */ | |
129 | static void isolate_freepages(struct zone *zone, | |
130 | struct compact_control *cc) | |
131 | { | |
132 | struct page *page; | |
133 | unsigned long high_pfn, low_pfn, pfn; | |
134 | unsigned long flags; | |
135 | int nr_freepages = cc->nr_freepages; | |
136 | struct list_head *freelist = &cc->freepages; | |
137 | ||
138 | pfn = cc->free_pfn; | |
139 | low_pfn = cc->migrate_pfn + pageblock_nr_pages; | |
140 | high_pfn = low_pfn; | |
141 | ||
142 | /* | |
143 | * Isolate free pages until enough are available to migrate the | |
144 | * pages on cc->migratepages. We stop searching if the migrate | |
145 | * and free page scanners meet or enough free pages are isolated. | |
146 | */ | |
147 | spin_lock_irqsave(&zone->lock, flags); | |
148 | for (; pfn > low_pfn && cc->nr_migratepages > nr_freepages; | |
149 | pfn -= pageblock_nr_pages) { | |
150 | unsigned long isolated; | |
151 | ||
152 | if (!pfn_valid(pfn)) | |
153 | continue; | |
154 | ||
155 | /* | |
156 | * Check for overlapping nodes/zones. It's possible on some | |
157 | * configurations to have a setup like | |
158 | * node0 node1 node0 | |
159 | * i.e. it's possible that all pages within a zones range of | |
160 | * pages do not belong to a single zone. | |
161 | */ | |
162 | page = pfn_to_page(pfn); | |
163 | if (page_zone(page) != zone) | |
164 | continue; | |
165 | ||
166 | /* Check the block is suitable for migration */ | |
167 | if (!suitable_migration_target(page)) | |
168 | continue; | |
169 | ||
170 | /* Found a block suitable for isolating free pages from */ | |
171 | isolated = isolate_freepages_block(zone, pfn, freelist); | |
172 | nr_freepages += isolated; | |
173 | ||
174 | /* | |
175 | * Record the highest PFN we isolated pages from. When next | |
176 | * looking for free pages, the search will restart here as | |
177 | * page migration may have returned some pages to the allocator | |
178 | */ | |
179 | if (isolated) | |
180 | high_pfn = max(high_pfn, pfn); | |
181 | } | |
182 | spin_unlock_irqrestore(&zone->lock, flags); | |
183 | ||
184 | /* split_free_page does not map the pages */ | |
185 | list_for_each_entry(page, freelist, lru) { | |
186 | arch_alloc_page(page, 0); | |
187 | kernel_map_pages(page, 1, 1); | |
188 | } | |
189 | ||
190 | cc->free_pfn = high_pfn; | |
191 | cc->nr_freepages = nr_freepages; | |
192 | } | |
193 | ||
194 | /* Update the number of anon and file isolated pages in the zone */ | |
195 | static void acct_isolated(struct zone *zone, struct compact_control *cc) | |
196 | { | |
197 | struct page *page; | |
198 | unsigned int count[NR_LRU_LISTS] = { 0, }; | |
199 | ||
200 | list_for_each_entry(page, &cc->migratepages, lru) { | |
201 | int lru = page_lru_base_type(page); | |
202 | count[lru]++; | |
203 | } | |
204 | ||
205 | cc->nr_anon = count[LRU_ACTIVE_ANON] + count[LRU_INACTIVE_ANON]; | |
206 | cc->nr_file = count[LRU_ACTIVE_FILE] + count[LRU_INACTIVE_FILE]; | |
207 | __mod_zone_page_state(zone, NR_ISOLATED_ANON, cc->nr_anon); | |
208 | __mod_zone_page_state(zone, NR_ISOLATED_FILE, cc->nr_file); | |
209 | } | |
210 | ||
211 | /* Similar to reclaim, but different enough that they don't share logic */ | |
212 | static bool too_many_isolated(struct zone *zone) | |
213 | { | |
214 | ||
215 | unsigned long inactive, isolated; | |
216 | ||
217 | inactive = zone_page_state(zone, NR_INACTIVE_FILE) + | |
218 | zone_page_state(zone, NR_INACTIVE_ANON); | |
219 | isolated = zone_page_state(zone, NR_ISOLATED_FILE) + | |
220 | zone_page_state(zone, NR_ISOLATED_ANON); | |
221 | ||
222 | return isolated > inactive; | |
223 | } | |
224 | ||
225 | /* | |
226 | * Isolate all pages that can be migrated from the block pointed to by | |
227 | * the migrate scanner within compact_control. | |
228 | */ | |
229 | static unsigned long isolate_migratepages(struct zone *zone, | |
230 | struct compact_control *cc) | |
231 | { | |
232 | unsigned long low_pfn, end_pfn; | |
233 | struct list_head *migratelist = &cc->migratepages; | |
234 | ||
235 | /* Do not scan outside zone boundaries */ | |
236 | low_pfn = max(cc->migrate_pfn, zone->zone_start_pfn); | |
237 | ||
238 | /* Only scan within a pageblock boundary */ | |
239 | end_pfn = ALIGN(low_pfn + pageblock_nr_pages, pageblock_nr_pages); | |
240 | ||
241 | /* Do not cross the free scanner or scan within a memory hole */ | |
242 | if (end_pfn > cc->free_pfn || !pfn_valid(low_pfn)) { | |
243 | cc->migrate_pfn = end_pfn; | |
244 | return 0; | |
245 | } | |
246 | ||
247 | /* | |
248 | * Ensure that there are not too many pages isolated from the LRU | |
249 | * list by either parallel reclaimers or compaction. If there are, | |
250 | * delay for some time until fewer pages are isolated | |
251 | */ | |
252 | while (unlikely(too_many_isolated(zone))) { | |
253 | congestion_wait(BLK_RW_ASYNC, HZ/10); | |
254 | ||
255 | if (fatal_signal_pending(current)) | |
256 | return 0; | |
257 | } | |
258 | ||
259 | /* Time to isolate some pages for migration */ | |
260 | spin_lock_irq(&zone->lru_lock); | |
261 | for (; low_pfn < end_pfn; low_pfn++) { | |
262 | struct page *page; | |
263 | if (!pfn_valid_within(low_pfn)) | |
264 | continue; | |
265 | ||
266 | /* Get the page and skip if free */ | |
267 | page = pfn_to_page(low_pfn); | |
268 | if (PageBuddy(page)) | |
269 | continue; | |
270 | ||
271 | /* Try isolate the page */ | |
272 | if (__isolate_lru_page(page, ISOLATE_BOTH, 0) != 0) | |
273 | continue; | |
274 | ||
275 | /* Successfully isolated */ | |
276 | del_page_from_lru_list(zone, page, page_lru(page)); | |
277 | list_add(&page->lru, migratelist); | |
278 | mem_cgroup_del_lru(page); | |
279 | cc->nr_migratepages++; | |
280 | ||
281 | /* Avoid isolating too much */ | |
282 | if (cc->nr_migratepages == COMPACT_CLUSTER_MAX) | |
283 | break; | |
284 | } | |
285 | ||
286 | acct_isolated(zone, cc); | |
287 | ||
288 | spin_unlock_irq(&zone->lru_lock); | |
289 | cc->migrate_pfn = low_pfn; | |
290 | ||
291 | return cc->nr_migratepages; | |
292 | } | |
293 | ||
294 | /* | |
295 | * This is a migrate-callback that "allocates" freepages by taking pages | |
296 | * from the isolated freelists in the block we are migrating to. | |
297 | */ | |
298 | static struct page *compaction_alloc(struct page *migratepage, | |
299 | unsigned long data, | |
300 | int **result) | |
301 | { | |
302 | struct compact_control *cc = (struct compact_control *)data; | |
303 | struct page *freepage; | |
304 | ||
305 | /* Isolate free pages if necessary */ | |
306 | if (list_empty(&cc->freepages)) { | |
307 | isolate_freepages(cc->zone, cc); | |
308 | ||
309 | if (list_empty(&cc->freepages)) | |
310 | return NULL; | |
311 | } | |
312 | ||
313 | freepage = list_entry(cc->freepages.next, struct page, lru); | |
314 | list_del(&freepage->lru); | |
315 | cc->nr_freepages--; | |
316 | ||
317 | return freepage; | |
318 | } | |
319 | ||
320 | /* | |
321 | * We cannot control nr_migratepages and nr_freepages fully when migration is | |
322 | * running as migrate_pages() has no knowledge of compact_control. When | |
323 | * migration is complete, we count the number of pages on the lists by hand. | |
324 | */ | |
325 | static void update_nr_listpages(struct compact_control *cc) | |
326 | { | |
327 | int nr_migratepages = 0; | |
328 | int nr_freepages = 0; | |
329 | struct page *page; | |
330 | ||
331 | list_for_each_entry(page, &cc->migratepages, lru) | |
332 | nr_migratepages++; | |
333 | list_for_each_entry(page, &cc->freepages, lru) | |
334 | nr_freepages++; | |
335 | ||
336 | cc->nr_migratepages = nr_migratepages; | |
337 | cc->nr_freepages = nr_freepages; | |
338 | } | |
339 | ||
340 | static int compact_finished(struct zone *zone, | |
341 | struct compact_control *cc) | |
342 | { | |
343 | if (fatal_signal_pending(current)) | |
344 | return COMPACT_PARTIAL; | |
345 | ||
346 | /* Compaction run completes if the migrate and free scanner meet */ | |
347 | if (cc->free_pfn <= cc->migrate_pfn) | |
348 | return COMPACT_COMPLETE; | |
349 | ||
350 | return COMPACT_CONTINUE; | |
351 | } | |
352 | ||
353 | static int compact_zone(struct zone *zone, struct compact_control *cc) | |
354 | { | |
355 | int ret; | |
356 | ||
357 | /* Setup to move all movable pages to the end of the zone */ | |
358 | cc->migrate_pfn = zone->zone_start_pfn; | |
359 | cc->free_pfn = cc->migrate_pfn + zone->spanned_pages; | |
360 | cc->free_pfn &= ~(pageblock_nr_pages-1); | |
361 | ||
362 | migrate_prep_local(); | |
363 | ||
364 | while ((ret = compact_finished(zone, cc)) == COMPACT_CONTINUE) { | |
365 | unsigned long nr_migrate, nr_remaining; | |
366 | ||
367 | if (!isolate_migratepages(zone, cc)) | |
368 | continue; | |
369 | ||
370 | nr_migrate = cc->nr_migratepages; | |
371 | migrate_pages(&cc->migratepages, compaction_alloc, | |
372 | (unsigned long)cc, 0); | |
373 | update_nr_listpages(cc); | |
374 | nr_remaining = cc->nr_migratepages; | |
375 | ||
376 | count_vm_event(COMPACTBLOCKS); | |
377 | count_vm_events(COMPACTPAGES, nr_migrate - nr_remaining); | |
378 | if (nr_remaining) | |
379 | count_vm_events(COMPACTPAGEFAILED, nr_remaining); | |
380 | ||
381 | /* Release LRU pages not migrated */ | |
382 | if (!list_empty(&cc->migratepages)) { | |
383 | putback_lru_pages(&cc->migratepages); | |
384 | cc->nr_migratepages = 0; | |
385 | } | |
386 | ||
387 | } | |
388 | ||
389 | /* Release free pages and check accounting */ | |
390 | cc->nr_freepages -= release_freepages(&cc->freepages); | |
391 | VM_BUG_ON(cc->nr_freepages != 0); | |
392 | ||
393 | return ret; | |
394 | } | |
76ab0f53 MG |
395 | |
396 | /* Compact all zones within a node */ | |
397 | static int compact_node(int nid) | |
398 | { | |
399 | int zoneid; | |
400 | pg_data_t *pgdat; | |
401 | struct zone *zone; | |
402 | ||
403 | if (nid < 0 || nid >= nr_node_ids || !node_online(nid)) | |
404 | return -EINVAL; | |
405 | pgdat = NODE_DATA(nid); | |
406 | ||
407 | /* Flush pending updates to the LRU lists */ | |
408 | lru_add_drain_all(); | |
409 | ||
410 | for (zoneid = 0; zoneid < MAX_NR_ZONES; zoneid++) { | |
411 | struct compact_control cc = { | |
412 | .nr_freepages = 0, | |
413 | .nr_migratepages = 0, | |
414 | }; | |
415 | ||
416 | zone = &pgdat->node_zones[zoneid]; | |
417 | if (!populated_zone(zone)) | |
418 | continue; | |
419 | ||
420 | cc.zone = zone; | |
421 | INIT_LIST_HEAD(&cc.freepages); | |
422 | INIT_LIST_HEAD(&cc.migratepages); | |
423 | ||
424 | compact_zone(zone, &cc); | |
425 | ||
426 | VM_BUG_ON(!list_empty(&cc.freepages)); | |
427 | VM_BUG_ON(!list_empty(&cc.migratepages)); | |
428 | } | |
429 | ||
430 | return 0; | |
431 | } | |
432 | ||
433 | /* Compact all nodes in the system */ | |
434 | static int compact_nodes(void) | |
435 | { | |
436 | int nid; | |
437 | ||
438 | for_each_online_node(nid) | |
439 | compact_node(nid); | |
440 | ||
441 | return COMPACT_COMPLETE; | |
442 | } | |
443 | ||
444 | /* The written value is actually unused, all memory is compacted */ | |
445 | int sysctl_compact_memory; | |
446 | ||
447 | /* This is the entry point for compacting all nodes via /proc/sys/vm */ | |
448 | int sysctl_compaction_handler(struct ctl_table *table, int write, | |
449 | void __user *buffer, size_t *length, loff_t *ppos) | |
450 | { | |
451 | if (write) | |
452 | return compact_nodes(); | |
453 | ||
454 | return 0; | |
455 | } |