mm: have zonelist contains structs with both a zone pointer and zone_idx
[sfrench/cifs-2.6.git] / mm / mempolicy.c
1 /*
2  * Simple NUMA memory policy for the Linux kernel.
3  *
4  * Copyright 2003,2004 Andi Kleen, SuSE Labs.
5  * (C) Copyright 2005 Christoph Lameter, Silicon Graphics, Inc.
6  * Subject to the GNU Public License, version 2.
7  *
8  * NUMA policy allows the user to give hints in which node(s) memory should
9  * be allocated.
10  *
11  * Support four policies per VMA and per process:
12  *
13  * The VMA policy has priority over the process policy for a page fault.
14  *
15  * interleave     Allocate memory interleaved over a set of nodes,
16  *                with normal fallback if it fails.
17  *                For VMA based allocations this interleaves based on the
18  *                offset into the backing object or offset into the mapping
19  *                for anonymous memory. For process policy an process counter
20  *                is used.
21  *
22  * bind           Only allocate memory on a specific set of nodes,
23  *                no fallback.
24  *                FIXME: memory is allocated starting with the first node
25  *                to the last. It would be better if bind would truly restrict
26  *                the allocation to memory nodes instead
27  *
28  * preferred       Try a specific node first before normal fallback.
29  *                As a special case node -1 here means do the allocation
30  *                on the local CPU. This is normally identical to default,
31  *                but useful to set in a VMA when you have a non default
32  *                process policy.
33  *
34  * default        Allocate on the local node first, or when on a VMA
35  *                use the process policy. This is what Linux always did
36  *                in a NUMA aware kernel and still does by, ahem, default.
37  *
38  * The process policy is applied for most non interrupt memory allocations
39  * in that process' context. Interrupts ignore the policies and always
40  * try to allocate on the local CPU. The VMA policy is only applied for memory
41  * allocations for a VMA in the VM.
42  *
43  * Currently there are a few corner cases in swapping where the policy
44  * is not applied, but the majority should be handled. When process policy
45  * is used it is not remembered over swap outs/swap ins.
46  *
47  * Only the highest zone in the zone hierarchy gets policied. Allocations
48  * requesting a lower zone just use default policy. This implies that
49  * on systems with highmem kernel lowmem allocation don't get policied.
50  * Same with GFP_DMA allocations.
51  *
52  * For shmfs/tmpfs/hugetlbfs shared memory the policy is shared between
53  * all users and remembered even when nobody has memory mapped.
54  */
55
56 /* Notebook:
57    fix mmap readahead to honour policy and enable policy for any page cache
58    object
59    statistics for bigpages
60    global policy for page cache? currently it uses process policy. Requires
61    first item above.
62    handle mremap for shared memory (currently ignored for the policy)
63    grows down?
64    make bind policy root only? It can trigger oom much faster and the
65    kernel is not always grateful with that.
66    could replace all the switch()es with a mempolicy_ops structure.
67 */
68
69 #include <linux/mempolicy.h>
70 #include <linux/mm.h>
71 #include <linux/highmem.h>
72 #include <linux/hugetlb.h>
73 #include <linux/kernel.h>
74 #include <linux/sched.h>
75 #include <linux/nodemask.h>
76 #include <linux/cpuset.h>
77 #include <linux/gfp.h>
78 #include <linux/slab.h>
79 #include <linux/string.h>
80 #include <linux/module.h>
81 #include <linux/nsproxy.h>
82 #include <linux/interrupt.h>
83 #include <linux/init.h>
84 #include <linux/compat.h>
85 #include <linux/swap.h>
86 #include <linux/seq_file.h>
87 #include <linux/proc_fs.h>
88 #include <linux/migrate.h>
89 #include <linux/rmap.h>
90 #include <linux/security.h>
91 #include <linux/syscalls.h>
92
93 #include <asm/tlbflush.h>
94 #include <asm/uaccess.h>
95
96 /* Internal flags */
97 #define MPOL_MF_DISCONTIG_OK (MPOL_MF_INTERNAL << 0)    /* Skip checks for continuous vmas */
98 #define MPOL_MF_INVERT (MPOL_MF_INTERNAL << 1)          /* Invert check for nodemask */
99 #define MPOL_MF_STATS (MPOL_MF_INTERNAL << 2)           /* Gather statistics */
100
101 static struct kmem_cache *policy_cache;
102 static struct kmem_cache *sn_cache;
103
104 /* Highest zone. An specific allocation for a zone below that is not
105    policied. */
106 enum zone_type policy_zone = 0;
107
108 struct mempolicy default_policy = {
109         .refcnt = ATOMIC_INIT(1), /* never free it */
110         .policy = MPOL_DEFAULT,
111 };
112
113 static void mpol_rebind_policy(struct mempolicy *pol,
114                                const nodemask_t *newmask);
115
116 /* Do sanity checking on a policy */
117 static int mpol_check_policy(int mode, nodemask_t *nodes)
118 {
119         int was_empty, is_empty;
120
121         if (!nodes)
122                 return 0;
123
124         /*
125          * "Contextualize" the in-coming nodemast for cpusets:
126          * Remember whether in-coming nodemask was empty,  If not,
127          * restrict the nodes to the allowed nodes in the cpuset.
128          * This is guaranteed to be a subset of nodes with memory.
129          */
130         cpuset_update_task_memory_state();
131         is_empty = was_empty = nodes_empty(*nodes);
132         if (!was_empty) {
133                 nodes_and(*nodes, *nodes, cpuset_current_mems_allowed);
134                 is_empty = nodes_empty(*nodes); /* after "contextualization" */
135         }
136
137         switch (mode) {
138         case MPOL_DEFAULT:
139                 /*
140                  * require caller to specify an empty nodemask
141                  * before "contextualization"
142                  */
143                 if (!was_empty)
144                         return -EINVAL;
145                 break;
146         case MPOL_BIND:
147         case MPOL_INTERLEAVE:
148                 /*
149                  * require at least 1 valid node after "contextualization"
150                  */
151                 if (is_empty)
152                         return -EINVAL;
153                 break;
154         case MPOL_PREFERRED:
155                 /*
156                  * Did caller specify invalid nodes?
157                  * Don't silently accept this as "local allocation".
158                  */
159                 if (!was_empty && is_empty)
160                         return -EINVAL;
161                 break;
162         }
163         return 0;
164 }
165
166 /* Generate a custom zonelist for the BIND policy. */
167 static struct zonelist *bind_zonelist(nodemask_t *nodes)
168 {
169         struct zonelist *zl;
170         int num, max, nd;
171         enum zone_type k;
172
173         max = 1 + MAX_NR_ZONES * nodes_weight(*nodes);
174         max++;                  /* space for zlcache_ptr (see mmzone.h) */
175         zl = kmalloc(sizeof(struct zone *) * max, GFP_KERNEL);
176         if (!zl)
177                 return ERR_PTR(-ENOMEM);
178         zl->zlcache_ptr = NULL;
179         num = 0;
180         /* First put in the highest zones from all nodes, then all the next 
181            lower zones etc. Avoid empty zones because the memory allocator
182            doesn't like them. If you implement node hot removal you
183            have to fix that. */
184         k = MAX_NR_ZONES - 1;
185         while (1) {
186                 for_each_node_mask(nd, *nodes) { 
187                         struct zone *z = &NODE_DATA(nd)->node_zones[k];
188                         if (z->present_pages > 0) 
189                                 zoneref_set_zone(z, &zl->_zonerefs[num++]);
190                 }
191                 if (k == 0)
192                         break;
193                 k--;
194         }
195         if (num == 0) {
196                 kfree(zl);
197                 return ERR_PTR(-EINVAL);
198         }
199         zl->_zonerefs[num].zone = NULL;
200         zl->_zonerefs[num].zone_idx = 0;
201         return zl;
202 }
203
204 /* Create a new policy */
205 static struct mempolicy *mpol_new(int mode, nodemask_t *nodes)
206 {
207         struct mempolicy *policy;
208
209         pr_debug("setting mode %d nodes[0] %lx\n",
210                  mode, nodes ? nodes_addr(*nodes)[0] : -1);
211
212         if (mode == MPOL_DEFAULT)
213                 return NULL;
214         policy = kmem_cache_alloc(policy_cache, GFP_KERNEL);
215         if (!policy)
216                 return ERR_PTR(-ENOMEM);
217         atomic_set(&policy->refcnt, 1);
218         switch (mode) {
219         case MPOL_INTERLEAVE:
220                 policy->v.nodes = *nodes;
221                 if (nodes_weight(policy->v.nodes) == 0) {
222                         kmem_cache_free(policy_cache, policy);
223                         return ERR_PTR(-EINVAL);
224                 }
225                 break;
226         case MPOL_PREFERRED:
227                 policy->v.preferred_node = first_node(*nodes);
228                 if (policy->v.preferred_node >= MAX_NUMNODES)
229                         policy->v.preferred_node = -1;
230                 break;
231         case MPOL_BIND:
232                 policy->v.zonelist = bind_zonelist(nodes);
233                 if (IS_ERR(policy->v.zonelist)) {
234                         void *error_code = policy->v.zonelist;
235                         kmem_cache_free(policy_cache, policy);
236                         return error_code;
237                 }
238                 break;
239         }
240         policy->policy = mode;
241         policy->cpuset_mems_allowed = cpuset_mems_allowed(current);
242         return policy;
243 }
244
245 static void gather_stats(struct page *, void *, int pte_dirty);
246 static void migrate_page_add(struct page *page, struct list_head *pagelist,
247                                 unsigned long flags);
248
249 /* Scan through pages checking if pages follow certain conditions. */
250 static int check_pte_range(struct vm_area_struct *vma, pmd_t *pmd,
251                 unsigned long addr, unsigned long end,
252                 const nodemask_t *nodes, unsigned long flags,
253                 void *private)
254 {
255         pte_t *orig_pte;
256         pte_t *pte;
257         spinlock_t *ptl;
258
259         orig_pte = pte = pte_offset_map_lock(vma->vm_mm, pmd, addr, &ptl);
260         do {
261                 struct page *page;
262                 int nid;
263
264                 if (!pte_present(*pte))
265                         continue;
266                 page = vm_normal_page(vma, addr, *pte);
267                 if (!page)
268                         continue;
269                 /*
270                  * The check for PageReserved here is important to avoid
271                  * handling zero pages and other pages that may have been
272                  * marked special by the system.
273                  *
274                  * If the PageReserved would not be checked here then f.e.
275                  * the location of the zero page could have an influence
276                  * on MPOL_MF_STRICT, zero pages would be counted for
277                  * the per node stats, and there would be useless attempts
278                  * to put zero pages on the migration list.
279                  */
280                 if (PageReserved(page))
281                         continue;
282                 nid = page_to_nid(page);
283                 if (node_isset(nid, *nodes) == !!(flags & MPOL_MF_INVERT))
284                         continue;
285
286                 if (flags & MPOL_MF_STATS)
287                         gather_stats(page, private, pte_dirty(*pte));
288                 else if (flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL))
289                         migrate_page_add(page, private, flags);
290                 else
291                         break;
292         } while (pte++, addr += PAGE_SIZE, addr != end);
293         pte_unmap_unlock(orig_pte, ptl);
294         return addr != end;
295 }
296
297 static inline int check_pmd_range(struct vm_area_struct *vma, pud_t *pud,
298                 unsigned long addr, unsigned long end,
299                 const nodemask_t *nodes, unsigned long flags,
300                 void *private)
301 {
302         pmd_t *pmd;
303         unsigned long next;
304
305         pmd = pmd_offset(pud, addr);
306         do {
307                 next = pmd_addr_end(addr, end);
308                 if (pmd_none_or_clear_bad(pmd))
309                         continue;
310                 if (check_pte_range(vma, pmd, addr, next, nodes,
311                                     flags, private))
312                         return -EIO;
313         } while (pmd++, addr = next, addr != end);
314         return 0;
315 }
316
317 static inline int check_pud_range(struct vm_area_struct *vma, pgd_t *pgd,
318                 unsigned long addr, unsigned long end,
319                 const nodemask_t *nodes, unsigned long flags,
320                 void *private)
321 {
322         pud_t *pud;
323         unsigned long next;
324
325         pud = pud_offset(pgd, addr);
326         do {
327                 next = pud_addr_end(addr, end);
328                 if (pud_none_or_clear_bad(pud))
329                         continue;
330                 if (check_pmd_range(vma, pud, addr, next, nodes,
331                                     flags, private))
332                         return -EIO;
333         } while (pud++, addr = next, addr != end);
334         return 0;
335 }
336
337 static inline int check_pgd_range(struct vm_area_struct *vma,
338                 unsigned long addr, unsigned long end,
339                 const nodemask_t *nodes, unsigned long flags,
340                 void *private)
341 {
342         pgd_t *pgd;
343         unsigned long next;
344
345         pgd = pgd_offset(vma->vm_mm, addr);
346         do {
347                 next = pgd_addr_end(addr, end);
348                 if (pgd_none_or_clear_bad(pgd))
349                         continue;
350                 if (check_pud_range(vma, pgd, addr, next, nodes,
351                                     flags, private))
352                         return -EIO;
353         } while (pgd++, addr = next, addr != end);
354         return 0;
355 }
356
357 /*
358  * Check if all pages in a range are on a set of nodes.
359  * If pagelist != NULL then isolate pages from the LRU and
360  * put them on the pagelist.
361  */
362 static struct vm_area_struct *
363 check_range(struct mm_struct *mm, unsigned long start, unsigned long end,
364                 const nodemask_t *nodes, unsigned long flags, void *private)
365 {
366         int err;
367         struct vm_area_struct *first, *vma, *prev;
368
369         if (flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)) {
370
371                 err = migrate_prep();
372                 if (err)
373                         return ERR_PTR(err);
374         }
375
376         first = find_vma(mm, start);
377         if (!first)
378                 return ERR_PTR(-EFAULT);
379         prev = NULL;
380         for (vma = first; vma && vma->vm_start < end; vma = vma->vm_next) {
381                 if (!(flags & MPOL_MF_DISCONTIG_OK)) {
382                         if (!vma->vm_next && vma->vm_end < end)
383                                 return ERR_PTR(-EFAULT);
384                         if (prev && prev->vm_end < vma->vm_start)
385                                 return ERR_PTR(-EFAULT);
386                 }
387                 if (!is_vm_hugetlb_page(vma) &&
388                     ((flags & MPOL_MF_STRICT) ||
389                      ((flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)) &&
390                                 vma_migratable(vma)))) {
391                         unsigned long endvma = vma->vm_end;
392
393                         if (endvma > end)
394                                 endvma = end;
395                         if (vma->vm_start > start)
396                                 start = vma->vm_start;
397                         err = check_pgd_range(vma, start, endvma, nodes,
398                                                 flags, private);
399                         if (err) {
400                                 first = ERR_PTR(err);
401                                 break;
402                         }
403                 }
404                 prev = vma;
405         }
406         return first;
407 }
408
409 /* Apply policy to a single VMA */
410 static int policy_vma(struct vm_area_struct *vma, struct mempolicy *new)
411 {
412         int err = 0;
413         struct mempolicy *old = vma->vm_policy;
414
415         pr_debug("vma %lx-%lx/%lx vm_ops %p vm_file %p set_policy %p\n",
416                  vma->vm_start, vma->vm_end, vma->vm_pgoff,
417                  vma->vm_ops, vma->vm_file,
418                  vma->vm_ops ? vma->vm_ops->set_policy : NULL);
419
420         if (vma->vm_ops && vma->vm_ops->set_policy)
421                 err = vma->vm_ops->set_policy(vma, new);
422         if (!err) {
423                 mpol_get(new);
424                 vma->vm_policy = new;
425                 mpol_free(old);
426         }
427         return err;
428 }
429
430 /* Step 2: apply policy to a range and do splits. */
431 static int mbind_range(struct vm_area_struct *vma, unsigned long start,
432                        unsigned long end, struct mempolicy *new)
433 {
434         struct vm_area_struct *next;
435         int err;
436
437         err = 0;
438         for (; vma && vma->vm_start < end; vma = next) {
439                 next = vma->vm_next;
440                 if (vma->vm_start < start)
441                         err = split_vma(vma->vm_mm, vma, start, 1);
442                 if (!err && vma->vm_end > end)
443                         err = split_vma(vma->vm_mm, vma, end, 0);
444                 if (!err)
445                         err = policy_vma(vma, new);
446                 if (err)
447                         break;
448         }
449         return err;
450 }
451
452 /*
453  * Update task->flags PF_MEMPOLICY bit: set iff non-default
454  * mempolicy.  Allows more rapid checking of this (combined perhaps
455  * with other PF_* flag bits) on memory allocation hot code paths.
456  *
457  * If called from outside this file, the task 'p' should -only- be
458  * a newly forked child not yet visible on the task list, because
459  * manipulating the task flags of a visible task is not safe.
460  *
461  * The above limitation is why this routine has the funny name
462  * mpol_fix_fork_child_flag().
463  *
464  * It is also safe to call this with a task pointer of current,
465  * which the static wrapper mpol_set_task_struct_flag() does,
466  * for use within this file.
467  */
468
469 void mpol_fix_fork_child_flag(struct task_struct *p)
470 {
471         if (p->mempolicy)
472                 p->flags |= PF_MEMPOLICY;
473         else
474                 p->flags &= ~PF_MEMPOLICY;
475 }
476
477 static void mpol_set_task_struct_flag(void)
478 {
479         mpol_fix_fork_child_flag(current);
480 }
481
482 /* Set the process memory policy */
483 static long do_set_mempolicy(int mode, nodemask_t *nodes)
484 {
485         struct mempolicy *new;
486
487         if (mpol_check_policy(mode, nodes))
488                 return -EINVAL;
489         new = mpol_new(mode, nodes);
490         if (IS_ERR(new))
491                 return PTR_ERR(new);
492         mpol_free(current->mempolicy);
493         current->mempolicy = new;
494         mpol_set_task_struct_flag();
495         if (new && new->policy == MPOL_INTERLEAVE)
496                 current->il_next = first_node(new->v.nodes);
497         return 0;
498 }
499
500 /* Fill a zone bitmap for a policy */
501 static void get_zonemask(struct mempolicy *p, nodemask_t *nodes)
502 {
503         int i;
504
505         nodes_clear(*nodes);
506         switch (p->policy) {
507         case MPOL_BIND:
508                 for (i = 0; p->v.zonelist->_zonerefs[i].zone; i++) {
509                         struct zoneref *zref;
510                         zref = &p->v.zonelist->_zonerefs[i];
511                         node_set(zonelist_node_idx(zref), *nodes);
512                 }
513                 break;
514         case MPOL_DEFAULT:
515                 break;
516         case MPOL_INTERLEAVE:
517                 *nodes = p->v.nodes;
518                 break;
519         case MPOL_PREFERRED:
520                 /* or use current node instead of memory_map? */
521                 if (p->v.preferred_node < 0)
522                         *nodes = node_states[N_HIGH_MEMORY];
523                 else
524                         node_set(p->v.preferred_node, *nodes);
525                 break;
526         default:
527                 BUG();
528         }
529 }
530
531 static int lookup_node(struct mm_struct *mm, unsigned long addr)
532 {
533         struct page *p;
534         int err;
535
536         err = get_user_pages(current, mm, addr & PAGE_MASK, 1, 0, 0, &p, NULL);
537         if (err >= 0) {
538                 err = page_to_nid(p);
539                 put_page(p);
540         }
541         return err;
542 }
543
544 /* Retrieve NUMA policy */
545 static long do_get_mempolicy(int *policy, nodemask_t *nmask,
546                              unsigned long addr, unsigned long flags)
547 {
548         int err;
549         struct mm_struct *mm = current->mm;
550         struct vm_area_struct *vma = NULL;
551         struct mempolicy *pol = current->mempolicy;
552
553         cpuset_update_task_memory_state();
554         if (flags &
555                 ~(unsigned long)(MPOL_F_NODE|MPOL_F_ADDR|MPOL_F_MEMS_ALLOWED))
556                 return -EINVAL;
557
558         if (flags & MPOL_F_MEMS_ALLOWED) {
559                 if (flags & (MPOL_F_NODE|MPOL_F_ADDR))
560                         return -EINVAL;
561                 *policy = 0;    /* just so it's initialized */
562                 *nmask  = cpuset_current_mems_allowed;
563                 return 0;
564         }
565
566         if (flags & MPOL_F_ADDR) {
567                 down_read(&mm->mmap_sem);
568                 vma = find_vma_intersection(mm, addr, addr+1);
569                 if (!vma) {
570                         up_read(&mm->mmap_sem);
571                         return -EFAULT;
572                 }
573                 if (vma->vm_ops && vma->vm_ops->get_policy)
574                         pol = vma->vm_ops->get_policy(vma, addr);
575                 else
576                         pol = vma->vm_policy;
577         } else if (addr)
578                 return -EINVAL;
579
580         if (!pol)
581                 pol = &default_policy;
582
583         if (flags & MPOL_F_NODE) {
584                 if (flags & MPOL_F_ADDR) {
585                         err = lookup_node(mm, addr);
586                         if (err < 0)
587                                 goto out;
588                         *policy = err;
589                 } else if (pol == current->mempolicy &&
590                                 pol->policy == MPOL_INTERLEAVE) {
591                         *policy = current->il_next;
592                 } else {
593                         err = -EINVAL;
594                         goto out;
595                 }
596         } else
597                 *policy = pol->policy;
598
599         if (vma) {
600                 up_read(&current->mm->mmap_sem);
601                 vma = NULL;
602         }
603
604         err = 0;
605         if (nmask)
606                 get_zonemask(pol, nmask);
607
608  out:
609         if (vma)
610                 up_read(&current->mm->mmap_sem);
611         return err;
612 }
613
614 #ifdef CONFIG_MIGRATION
615 /*
616  * page migration
617  */
618 static void migrate_page_add(struct page *page, struct list_head *pagelist,
619                                 unsigned long flags)
620 {
621         /*
622          * Avoid migrating a page that is shared with others.
623          */
624         if ((flags & MPOL_MF_MOVE_ALL) || page_mapcount(page) == 1)
625                 isolate_lru_page(page, pagelist);
626 }
627
628 static struct page *new_node_page(struct page *page, unsigned long node, int **x)
629 {
630         return alloc_pages_node(node, GFP_HIGHUSER_MOVABLE, 0);
631 }
632
633 /*
634  * Migrate pages from one node to a target node.
635  * Returns error or the number of pages not migrated.
636  */
637 static int migrate_to_node(struct mm_struct *mm, int source, int dest,
638                            int flags)
639 {
640         nodemask_t nmask;
641         LIST_HEAD(pagelist);
642         int err = 0;
643
644         nodes_clear(nmask);
645         node_set(source, nmask);
646
647         check_range(mm, mm->mmap->vm_start, TASK_SIZE, &nmask,
648                         flags | MPOL_MF_DISCONTIG_OK, &pagelist);
649
650         if (!list_empty(&pagelist))
651                 err = migrate_pages(&pagelist, new_node_page, dest);
652
653         return err;
654 }
655
656 /*
657  * Move pages between the two nodesets so as to preserve the physical
658  * layout as much as possible.
659  *
660  * Returns the number of page that could not be moved.
661  */
662 int do_migrate_pages(struct mm_struct *mm,
663         const nodemask_t *from_nodes, const nodemask_t *to_nodes, int flags)
664 {
665         LIST_HEAD(pagelist);
666         int busy = 0;
667         int err = 0;
668         nodemask_t tmp;
669
670         down_read(&mm->mmap_sem);
671
672         err = migrate_vmas(mm, from_nodes, to_nodes, flags);
673         if (err)
674                 goto out;
675
676 /*
677  * Find a 'source' bit set in 'tmp' whose corresponding 'dest'
678  * bit in 'to' is not also set in 'tmp'.  Clear the found 'source'
679  * bit in 'tmp', and return that <source, dest> pair for migration.
680  * The pair of nodemasks 'to' and 'from' define the map.
681  *
682  * If no pair of bits is found that way, fallback to picking some
683  * pair of 'source' and 'dest' bits that are not the same.  If the
684  * 'source' and 'dest' bits are the same, this represents a node
685  * that will be migrating to itself, so no pages need move.
686  *
687  * If no bits are left in 'tmp', or if all remaining bits left
688  * in 'tmp' correspond to the same bit in 'to', return false
689  * (nothing left to migrate).
690  *
691  * This lets us pick a pair of nodes to migrate between, such that
692  * if possible the dest node is not already occupied by some other
693  * source node, minimizing the risk of overloading the memory on a
694  * node that would happen if we migrated incoming memory to a node
695  * before migrating outgoing memory source that same node.
696  *
697  * A single scan of tmp is sufficient.  As we go, we remember the
698  * most recent <s, d> pair that moved (s != d).  If we find a pair
699  * that not only moved, but what's better, moved to an empty slot
700  * (d is not set in tmp), then we break out then, with that pair.
701  * Otherwise when we finish scannng from_tmp, we at least have the
702  * most recent <s, d> pair that moved.  If we get all the way through
703  * the scan of tmp without finding any node that moved, much less
704  * moved to an empty node, then there is nothing left worth migrating.
705  */
706
707         tmp = *from_nodes;
708         while (!nodes_empty(tmp)) {
709                 int s,d;
710                 int source = -1;
711                 int dest = 0;
712
713                 for_each_node_mask(s, tmp) {
714                         d = node_remap(s, *from_nodes, *to_nodes);
715                         if (s == d)
716                                 continue;
717
718                         source = s;     /* Node moved. Memorize */
719                         dest = d;
720
721                         /* dest not in remaining from nodes? */
722                         if (!node_isset(dest, tmp))
723                                 break;
724                 }
725                 if (source == -1)
726                         break;
727
728                 node_clear(source, tmp);
729                 err = migrate_to_node(mm, source, dest, flags);
730                 if (err > 0)
731                         busy += err;
732                 if (err < 0)
733                         break;
734         }
735 out:
736         up_read(&mm->mmap_sem);
737         if (err < 0)
738                 return err;
739         return busy;
740
741 }
742
743 /*
744  * Allocate a new page for page migration based on vma policy.
745  * Start assuming that page is mapped by vma pointed to by @private.
746  * Search forward from there, if not.  N.B., this assumes that the
747  * list of pages handed to migrate_pages()--which is how we get here--
748  * is in virtual address order.
749  */
750 static struct page *new_vma_page(struct page *page, unsigned long private, int **x)
751 {
752         struct vm_area_struct *vma = (struct vm_area_struct *)private;
753         unsigned long uninitialized_var(address);
754
755         while (vma) {
756                 address = page_address_in_vma(page, vma);
757                 if (address != -EFAULT)
758                         break;
759                 vma = vma->vm_next;
760         }
761
762         /*
763          * if !vma, alloc_page_vma() will use task or system default policy
764          */
765         return alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address);
766 }
767 #else
768
769 static void migrate_page_add(struct page *page, struct list_head *pagelist,
770                                 unsigned long flags)
771 {
772 }
773
774 int do_migrate_pages(struct mm_struct *mm,
775         const nodemask_t *from_nodes, const nodemask_t *to_nodes, int flags)
776 {
777         return -ENOSYS;
778 }
779
780 static struct page *new_vma_page(struct page *page, unsigned long private, int **x)
781 {
782         return NULL;
783 }
784 #endif
785
786 static long do_mbind(unsigned long start, unsigned long len,
787                      unsigned long mode, nodemask_t *nmask,
788                      unsigned long flags)
789 {
790         struct vm_area_struct *vma;
791         struct mm_struct *mm = current->mm;
792         struct mempolicy *new;
793         unsigned long end;
794         int err;
795         LIST_HEAD(pagelist);
796
797         if ((flags & ~(unsigned long)(MPOL_MF_STRICT |
798                                       MPOL_MF_MOVE | MPOL_MF_MOVE_ALL))
799             || mode > MPOL_MAX)
800                 return -EINVAL;
801         if ((flags & MPOL_MF_MOVE_ALL) && !capable(CAP_SYS_NICE))
802                 return -EPERM;
803
804         if (start & ~PAGE_MASK)
805                 return -EINVAL;
806
807         if (mode == MPOL_DEFAULT)
808                 flags &= ~MPOL_MF_STRICT;
809
810         len = (len + PAGE_SIZE - 1) & PAGE_MASK;
811         end = start + len;
812
813         if (end < start)
814                 return -EINVAL;
815         if (end == start)
816                 return 0;
817
818         if (mpol_check_policy(mode, nmask))
819                 return -EINVAL;
820
821         new = mpol_new(mode, nmask);
822         if (IS_ERR(new))
823                 return PTR_ERR(new);
824
825         /*
826          * If we are using the default policy then operation
827          * on discontinuous address spaces is okay after all
828          */
829         if (!new)
830                 flags |= MPOL_MF_DISCONTIG_OK;
831
832         pr_debug("mbind %lx-%lx mode:%ld nodes:%lx\n",start,start+len,
833                  mode, nmask ? nodes_addr(*nmask)[0] : -1);
834
835         down_write(&mm->mmap_sem);
836         vma = check_range(mm, start, end, nmask,
837                           flags | MPOL_MF_INVERT, &pagelist);
838
839         err = PTR_ERR(vma);
840         if (!IS_ERR(vma)) {
841                 int nr_failed = 0;
842
843                 err = mbind_range(vma, start, end, new);
844
845                 if (!list_empty(&pagelist))
846                         nr_failed = migrate_pages(&pagelist, new_vma_page,
847                                                 (unsigned long)vma);
848
849                 if (!err && nr_failed && (flags & MPOL_MF_STRICT))
850                         err = -EIO;
851         }
852
853         up_write(&mm->mmap_sem);
854         mpol_free(new);
855         return err;
856 }
857
858 /*
859  * User space interface with variable sized bitmaps for nodelists.
860  */
861
862 /* Copy a node mask from user space. */
863 static int get_nodes(nodemask_t *nodes, const unsigned long __user *nmask,
864                      unsigned long maxnode)
865 {
866         unsigned long k;
867         unsigned long nlongs;
868         unsigned long endmask;
869
870         --maxnode;
871         nodes_clear(*nodes);
872         if (maxnode == 0 || !nmask)
873                 return 0;
874         if (maxnode > PAGE_SIZE*BITS_PER_BYTE)
875                 return -EINVAL;
876
877         nlongs = BITS_TO_LONGS(maxnode);
878         if ((maxnode % BITS_PER_LONG) == 0)
879                 endmask = ~0UL;
880         else
881                 endmask = (1UL << (maxnode % BITS_PER_LONG)) - 1;
882
883         /* When the user specified more nodes than supported just check
884            if the non supported part is all zero. */
885         if (nlongs > BITS_TO_LONGS(MAX_NUMNODES)) {
886                 if (nlongs > PAGE_SIZE/sizeof(long))
887                         return -EINVAL;
888                 for (k = BITS_TO_LONGS(MAX_NUMNODES); k < nlongs; k++) {
889                         unsigned long t;
890                         if (get_user(t, nmask + k))
891                                 return -EFAULT;
892                         if (k == nlongs - 1) {
893                                 if (t & endmask)
894                                         return -EINVAL;
895                         } else if (t)
896                                 return -EINVAL;
897                 }
898                 nlongs = BITS_TO_LONGS(MAX_NUMNODES);
899                 endmask = ~0UL;
900         }
901
902         if (copy_from_user(nodes_addr(*nodes), nmask, nlongs*sizeof(unsigned long)))
903                 return -EFAULT;
904         nodes_addr(*nodes)[nlongs-1] &= endmask;
905         return 0;
906 }
907
908 /* Copy a kernel node mask to user space */
909 static int copy_nodes_to_user(unsigned long __user *mask, unsigned long maxnode,
910                               nodemask_t *nodes)
911 {
912         unsigned long copy = ALIGN(maxnode-1, 64) / 8;
913         const int nbytes = BITS_TO_LONGS(MAX_NUMNODES) * sizeof(long);
914
915         if (copy > nbytes) {
916                 if (copy > PAGE_SIZE)
917                         return -EINVAL;
918                 if (clear_user((char __user *)mask + nbytes, copy - nbytes))
919                         return -EFAULT;
920                 copy = nbytes;
921         }
922         return copy_to_user(mask, nodes_addr(*nodes), copy) ? -EFAULT : 0;
923 }
924
925 asmlinkage long sys_mbind(unsigned long start, unsigned long len,
926                         unsigned long mode,
927                         unsigned long __user *nmask, unsigned long maxnode,
928                         unsigned flags)
929 {
930         nodemask_t nodes;
931         int err;
932
933         err = get_nodes(&nodes, nmask, maxnode);
934         if (err)
935                 return err;
936         return do_mbind(start, len, mode, &nodes, flags);
937 }
938
939 /* Set the process memory policy */
940 asmlinkage long sys_set_mempolicy(int mode, unsigned long __user *nmask,
941                 unsigned long maxnode)
942 {
943         int err;
944         nodemask_t nodes;
945
946         if (mode < 0 || mode > MPOL_MAX)
947                 return -EINVAL;
948         err = get_nodes(&nodes, nmask, maxnode);
949         if (err)
950                 return err;
951         return do_set_mempolicy(mode, &nodes);
952 }
953
954 asmlinkage long sys_migrate_pages(pid_t pid, unsigned long maxnode,
955                 const unsigned long __user *old_nodes,
956                 const unsigned long __user *new_nodes)
957 {
958         struct mm_struct *mm;
959         struct task_struct *task;
960         nodemask_t old;
961         nodemask_t new;
962         nodemask_t task_nodes;
963         int err;
964
965         err = get_nodes(&old, old_nodes, maxnode);
966         if (err)
967                 return err;
968
969         err = get_nodes(&new, new_nodes, maxnode);
970         if (err)
971                 return err;
972
973         /* Find the mm_struct */
974         read_lock(&tasklist_lock);
975         task = pid ? find_task_by_vpid(pid) : current;
976         if (!task) {
977                 read_unlock(&tasklist_lock);
978                 return -ESRCH;
979         }
980         mm = get_task_mm(task);
981         read_unlock(&tasklist_lock);
982
983         if (!mm)
984                 return -EINVAL;
985
986         /*
987          * Check if this process has the right to modify the specified
988          * process. The right exists if the process has administrative
989          * capabilities, superuser privileges or the same
990          * userid as the target process.
991          */
992         if ((current->euid != task->suid) && (current->euid != task->uid) &&
993             (current->uid != task->suid) && (current->uid != task->uid) &&
994             !capable(CAP_SYS_NICE)) {
995                 err = -EPERM;
996                 goto out;
997         }
998
999         task_nodes = cpuset_mems_allowed(task);
1000         /* Is the user allowed to access the target nodes? */
1001         if (!nodes_subset(new, task_nodes) && !capable(CAP_SYS_NICE)) {
1002                 err = -EPERM;
1003                 goto out;
1004         }
1005
1006         if (!nodes_subset(new, node_states[N_HIGH_MEMORY])) {
1007                 err = -EINVAL;
1008                 goto out;
1009         }
1010
1011         err = security_task_movememory(task);
1012         if (err)
1013                 goto out;
1014
1015         err = do_migrate_pages(mm, &old, &new,
1016                 capable(CAP_SYS_NICE) ? MPOL_MF_MOVE_ALL : MPOL_MF_MOVE);
1017 out:
1018         mmput(mm);
1019         return err;
1020 }
1021
1022
1023 /* Retrieve NUMA policy */
1024 asmlinkage long sys_get_mempolicy(int __user *policy,
1025                                 unsigned long __user *nmask,
1026                                 unsigned long maxnode,
1027                                 unsigned long addr, unsigned long flags)
1028 {
1029         int err;
1030         int uninitialized_var(pval);
1031         nodemask_t nodes;
1032
1033         if (nmask != NULL && maxnode < MAX_NUMNODES)
1034                 return -EINVAL;
1035
1036         err = do_get_mempolicy(&pval, &nodes, addr, flags);
1037
1038         if (err)
1039                 return err;
1040
1041         if (policy && put_user(pval, policy))
1042                 return -EFAULT;
1043
1044         if (nmask)
1045                 err = copy_nodes_to_user(nmask, maxnode, &nodes);
1046
1047         return err;
1048 }
1049
1050 #ifdef CONFIG_COMPAT
1051
1052 asmlinkage long compat_sys_get_mempolicy(int __user *policy,
1053                                      compat_ulong_t __user *nmask,
1054                                      compat_ulong_t maxnode,
1055                                      compat_ulong_t addr, compat_ulong_t flags)
1056 {
1057         long err;
1058         unsigned long __user *nm = NULL;
1059         unsigned long nr_bits, alloc_size;
1060         DECLARE_BITMAP(bm, MAX_NUMNODES);
1061
1062         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1063         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1064
1065         if (nmask)
1066                 nm = compat_alloc_user_space(alloc_size);
1067
1068         err = sys_get_mempolicy(policy, nm, nr_bits+1, addr, flags);
1069
1070         if (!err && nmask) {
1071                 err = copy_from_user(bm, nm, alloc_size);
1072                 /* ensure entire bitmap is zeroed */
1073                 err |= clear_user(nmask, ALIGN(maxnode-1, 8) / 8);
1074                 err |= compat_put_bitmap(nmask, bm, nr_bits);
1075         }
1076
1077         return err;
1078 }
1079
1080 asmlinkage long compat_sys_set_mempolicy(int mode, compat_ulong_t __user *nmask,
1081                                      compat_ulong_t maxnode)
1082 {
1083         long err = 0;
1084         unsigned long __user *nm = NULL;
1085         unsigned long nr_bits, alloc_size;
1086         DECLARE_BITMAP(bm, MAX_NUMNODES);
1087
1088         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1089         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1090
1091         if (nmask) {
1092                 err = compat_get_bitmap(bm, nmask, nr_bits);
1093                 nm = compat_alloc_user_space(alloc_size);
1094                 err |= copy_to_user(nm, bm, alloc_size);
1095         }
1096
1097         if (err)
1098                 return -EFAULT;
1099
1100         return sys_set_mempolicy(mode, nm, nr_bits+1);
1101 }
1102
1103 asmlinkage long compat_sys_mbind(compat_ulong_t start, compat_ulong_t len,
1104                              compat_ulong_t mode, compat_ulong_t __user *nmask,
1105                              compat_ulong_t maxnode, compat_ulong_t flags)
1106 {
1107         long err = 0;
1108         unsigned long __user *nm = NULL;
1109         unsigned long nr_bits, alloc_size;
1110         nodemask_t bm;
1111
1112         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1113         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1114
1115         if (nmask) {
1116                 err = compat_get_bitmap(nodes_addr(bm), nmask, nr_bits);
1117                 nm = compat_alloc_user_space(alloc_size);
1118                 err |= copy_to_user(nm, nodes_addr(bm), alloc_size);
1119         }
1120
1121         if (err)
1122                 return -EFAULT;
1123
1124         return sys_mbind(start, len, mode, nm, nr_bits+1, flags);
1125 }
1126
1127 #endif
1128
1129 /*
1130  * get_vma_policy(@task, @vma, @addr)
1131  * @task - task for fallback if vma policy == default
1132  * @vma   - virtual memory area whose policy is sought
1133  * @addr  - address in @vma for shared policy lookup
1134  *
1135  * Returns effective policy for a VMA at specified address.
1136  * Falls back to @task or system default policy, as necessary.
1137  * Returned policy has extra reference count if shared, vma,
1138  * or some other task's policy [show_numa_maps() can pass
1139  * @task != current].  It is the caller's responsibility to
1140  * free the reference in these cases.
1141  */
1142 static struct mempolicy * get_vma_policy(struct task_struct *task,
1143                 struct vm_area_struct *vma, unsigned long addr)
1144 {
1145         struct mempolicy *pol = task->mempolicy;
1146         int shared_pol = 0;
1147
1148         if (vma) {
1149                 if (vma->vm_ops && vma->vm_ops->get_policy) {
1150                         pol = vma->vm_ops->get_policy(vma, addr);
1151                         shared_pol = 1; /* if pol non-NULL, add ref below */
1152                 } else if (vma->vm_policy &&
1153                                 vma->vm_policy->policy != MPOL_DEFAULT)
1154                         pol = vma->vm_policy;
1155         }
1156         if (!pol)
1157                 pol = &default_policy;
1158         else if (!shared_pol && pol != current->mempolicy)
1159                 mpol_get(pol);  /* vma or other task's policy */
1160         return pol;
1161 }
1162
1163 /* Return a zonelist representing a mempolicy */
1164 static struct zonelist *zonelist_policy(gfp_t gfp, struct mempolicy *policy)
1165 {
1166         int nd;
1167
1168         switch (policy->policy) {
1169         case MPOL_PREFERRED:
1170                 nd = policy->v.preferred_node;
1171                 if (nd < 0)
1172                         nd = numa_node_id();
1173                 break;
1174         case MPOL_BIND:
1175                 /* Lower zones don't get a policy applied */
1176                 /* Careful: current->mems_allowed might have moved */
1177                 if (gfp_zone(gfp) >= policy_zone)
1178                         if (cpuset_zonelist_valid_mems_allowed(policy->v.zonelist))
1179                                 return policy->v.zonelist;
1180                 /*FALL THROUGH*/
1181         case MPOL_INTERLEAVE: /* should not happen */
1182         case MPOL_DEFAULT:
1183                 nd = numa_node_id();
1184                 break;
1185         default:
1186                 nd = 0;
1187                 BUG();
1188         }
1189         return node_zonelist(nd, gfp);
1190 }
1191
1192 /* Do dynamic interleaving for a process */
1193 static unsigned interleave_nodes(struct mempolicy *policy)
1194 {
1195         unsigned nid, next;
1196         struct task_struct *me = current;
1197
1198         nid = me->il_next;
1199         next = next_node(nid, policy->v.nodes);
1200         if (next >= MAX_NUMNODES)
1201                 next = first_node(policy->v.nodes);
1202         me->il_next = next;
1203         return nid;
1204 }
1205
1206 /*
1207  * Depending on the memory policy provide a node from which to allocate the
1208  * next slab entry.
1209  */
1210 unsigned slab_node(struct mempolicy *policy)
1211 {
1212         int pol = policy ? policy->policy : MPOL_DEFAULT;
1213
1214         switch (pol) {
1215         case MPOL_INTERLEAVE:
1216                 return interleave_nodes(policy);
1217
1218         case MPOL_BIND: {
1219                 /*
1220                  * Follow bind policy behavior and start allocation at the
1221                  * first node.
1222                  */
1223                 return zonelist_node_idx(policy->v.zonelist->_zonerefs);
1224         }
1225
1226         case MPOL_PREFERRED:
1227                 if (policy->v.preferred_node >= 0)
1228                         return policy->v.preferred_node;
1229                 /* Fall through */
1230
1231         default:
1232                 return numa_node_id();
1233         }
1234 }
1235
1236 /* Do static interleaving for a VMA with known offset. */
1237 static unsigned offset_il_node(struct mempolicy *pol,
1238                 struct vm_area_struct *vma, unsigned long off)
1239 {
1240         unsigned nnodes = nodes_weight(pol->v.nodes);
1241         unsigned target = (unsigned)off % nnodes;
1242         int c;
1243         int nid = -1;
1244
1245         c = 0;
1246         do {
1247                 nid = next_node(nid, pol->v.nodes);
1248                 c++;
1249         } while (c <= target);
1250         return nid;
1251 }
1252
1253 /* Determine a node number for interleave */
1254 static inline unsigned interleave_nid(struct mempolicy *pol,
1255                  struct vm_area_struct *vma, unsigned long addr, int shift)
1256 {
1257         if (vma) {
1258                 unsigned long off;
1259
1260                 /*
1261                  * for small pages, there is no difference between
1262                  * shift and PAGE_SHIFT, so the bit-shift is safe.
1263                  * for huge pages, since vm_pgoff is in units of small
1264                  * pages, we need to shift off the always 0 bits to get
1265                  * a useful offset.
1266                  */
1267                 BUG_ON(shift < PAGE_SHIFT);
1268                 off = vma->vm_pgoff >> (shift - PAGE_SHIFT);
1269                 off += (addr - vma->vm_start) >> shift;
1270                 return offset_il_node(pol, vma, off);
1271         } else
1272                 return interleave_nodes(pol);
1273 }
1274
1275 #ifdef CONFIG_HUGETLBFS
1276 /*
1277  * huge_zonelist(@vma, @addr, @gfp_flags, @mpol)
1278  * @vma = virtual memory area whose policy is sought
1279  * @addr = address in @vma for shared policy lookup and interleave policy
1280  * @gfp_flags = for requested zone
1281  * @mpol = pointer to mempolicy pointer for reference counted 'BIND policy
1282  *
1283  * Returns a zonelist suitable for a huge page allocation.
1284  * If the effective policy is 'BIND, returns pointer to policy's zonelist.
1285  * If it is also a policy for which get_vma_policy() returns an extra
1286  * reference, we must hold that reference until after allocation.
1287  * In that case, return policy via @mpol so hugetlb allocation can drop
1288  * the reference.  For non-'BIND referenced policies, we can/do drop the
1289  * reference here, so the caller doesn't need to know about the special case
1290  * for default and current task policy.
1291  */
1292 struct zonelist *huge_zonelist(struct vm_area_struct *vma, unsigned long addr,
1293                                 gfp_t gfp_flags, struct mempolicy **mpol)
1294 {
1295         struct mempolicy *pol = get_vma_policy(current, vma, addr);
1296         struct zonelist *zl;
1297
1298         *mpol = NULL;           /* probably no unref needed */
1299         if (pol->policy == MPOL_INTERLEAVE) {
1300                 unsigned nid;
1301
1302                 nid = interleave_nid(pol, vma, addr, HPAGE_SHIFT);
1303                 if (unlikely(pol != &default_policy &&
1304                                 pol != current->mempolicy))
1305                         __mpol_free(pol);       /* finished with pol */
1306                 return node_zonelist(nid, gfp_flags);
1307         }
1308
1309         zl = zonelist_policy(GFP_HIGHUSER, pol);
1310         if (unlikely(pol != &default_policy && pol != current->mempolicy)) {
1311                 if (pol->policy != MPOL_BIND)
1312                         __mpol_free(pol);       /* finished with pol */
1313                 else
1314                         *mpol = pol;    /* unref needed after allocation */
1315         }
1316         return zl;
1317 }
1318 #endif
1319
1320 /* Allocate a page in interleaved policy.
1321    Own path because it needs to do special accounting. */
1322 static struct page *alloc_page_interleave(gfp_t gfp, unsigned order,
1323                                         unsigned nid)
1324 {
1325         struct zonelist *zl;
1326         struct page *page;
1327
1328         zl = node_zonelist(nid, gfp);
1329         page = __alloc_pages(gfp, order, zl);
1330         if (page && page_zone(page) == zonelist_zone(&zl->_zonerefs[0]))
1331                 inc_zone_page_state(page, NUMA_INTERLEAVE_HIT);
1332         return page;
1333 }
1334
1335 /**
1336  *      alloc_page_vma  - Allocate a page for a VMA.
1337  *
1338  *      @gfp:
1339  *      %GFP_USER    user allocation.
1340  *      %GFP_KERNEL  kernel allocations,
1341  *      %GFP_HIGHMEM highmem/user allocations,
1342  *      %GFP_FS      allocation should not call back into a file system.
1343  *      %GFP_ATOMIC  don't sleep.
1344  *
1345  *      @vma:  Pointer to VMA or NULL if not available.
1346  *      @addr: Virtual Address of the allocation. Must be inside the VMA.
1347  *
1348  *      This function allocates a page from the kernel page pool and applies
1349  *      a NUMA policy associated with the VMA or the current process.
1350  *      When VMA is not NULL caller must hold down_read on the mmap_sem of the
1351  *      mm_struct of the VMA to prevent it from going away. Should be used for
1352  *      all allocations for pages that will be mapped into
1353  *      user space. Returns NULL when no page can be allocated.
1354  *
1355  *      Should be called with the mm_sem of the vma hold.
1356  */
1357 struct page *
1358 alloc_page_vma(gfp_t gfp, struct vm_area_struct *vma, unsigned long addr)
1359 {
1360         struct mempolicy *pol = get_vma_policy(current, vma, addr);
1361         struct zonelist *zl;
1362
1363         cpuset_update_task_memory_state();
1364
1365         if (unlikely(pol->policy == MPOL_INTERLEAVE)) {
1366                 unsigned nid;
1367
1368                 nid = interleave_nid(pol, vma, addr, PAGE_SHIFT);
1369                 if (unlikely(pol != &default_policy &&
1370                                 pol != current->mempolicy))
1371                         __mpol_free(pol);       /* finished with pol */
1372                 return alloc_page_interleave(gfp, 0, nid);
1373         }
1374         zl = zonelist_policy(gfp, pol);
1375         if (pol != &default_policy && pol != current->mempolicy) {
1376                 /*
1377                  * slow path: ref counted policy -- shared or vma
1378                  */
1379                 struct page *page =  __alloc_pages(gfp, 0, zl);
1380                 __mpol_free(pol);
1381                 return page;
1382         }
1383         /*
1384          * fast path:  default or task policy
1385          */
1386         return __alloc_pages(gfp, 0, zl);
1387 }
1388
1389 /**
1390  *      alloc_pages_current - Allocate pages.
1391  *
1392  *      @gfp:
1393  *              %GFP_USER   user allocation,
1394  *              %GFP_KERNEL kernel allocation,
1395  *              %GFP_HIGHMEM highmem allocation,
1396  *              %GFP_FS     don't call back into a file system.
1397  *              %GFP_ATOMIC don't sleep.
1398  *      @order: Power of two of allocation size in pages. 0 is a single page.
1399  *
1400  *      Allocate a page from the kernel page pool.  When not in
1401  *      interrupt context and apply the current process NUMA policy.
1402  *      Returns NULL when no page can be allocated.
1403  *
1404  *      Don't call cpuset_update_task_memory_state() unless
1405  *      1) it's ok to take cpuset_sem (can WAIT), and
1406  *      2) allocating for current task (not interrupt).
1407  */
1408 struct page *alloc_pages_current(gfp_t gfp, unsigned order)
1409 {
1410         struct mempolicy *pol = current->mempolicy;
1411
1412         if ((gfp & __GFP_WAIT) && !in_interrupt())
1413                 cpuset_update_task_memory_state();
1414         if (!pol || in_interrupt() || (gfp & __GFP_THISNODE))
1415                 pol = &default_policy;
1416         if (pol->policy == MPOL_INTERLEAVE)
1417                 return alloc_page_interleave(gfp, order, interleave_nodes(pol));
1418         return __alloc_pages(gfp, order, zonelist_policy(gfp, pol));
1419 }
1420 EXPORT_SYMBOL(alloc_pages_current);
1421
1422 /*
1423  * If mpol_copy() sees current->cpuset == cpuset_being_rebound, then it
1424  * rebinds the mempolicy its copying by calling mpol_rebind_policy()
1425  * with the mems_allowed returned by cpuset_mems_allowed().  This
1426  * keeps mempolicies cpuset relative after its cpuset moves.  See
1427  * further kernel/cpuset.c update_nodemask().
1428  */
1429
1430 /* Slow path of a mempolicy copy */
1431 struct mempolicy *__mpol_copy(struct mempolicy *old)
1432 {
1433         struct mempolicy *new = kmem_cache_alloc(policy_cache, GFP_KERNEL);
1434
1435         if (!new)
1436                 return ERR_PTR(-ENOMEM);
1437         if (current_cpuset_is_being_rebound()) {
1438                 nodemask_t mems = cpuset_mems_allowed(current);
1439                 mpol_rebind_policy(old, &mems);
1440         }
1441         *new = *old;
1442         atomic_set(&new->refcnt, 1);
1443         if (new->policy == MPOL_BIND) {
1444                 int sz = ksize(old->v.zonelist);
1445                 new->v.zonelist = kmemdup(old->v.zonelist, sz, GFP_KERNEL);
1446                 if (!new->v.zonelist) {
1447                         kmem_cache_free(policy_cache, new);
1448                         return ERR_PTR(-ENOMEM);
1449                 }
1450         }
1451         return new;
1452 }
1453
1454 /* Slow path of a mempolicy comparison */
1455 int __mpol_equal(struct mempolicy *a, struct mempolicy *b)
1456 {
1457         if (!a || !b)
1458                 return 0;
1459         if (a->policy != b->policy)
1460                 return 0;
1461         switch (a->policy) {
1462         case MPOL_DEFAULT:
1463                 return 1;
1464         case MPOL_INTERLEAVE:
1465                 return nodes_equal(a->v.nodes, b->v.nodes);
1466         case MPOL_PREFERRED:
1467                 return a->v.preferred_node == b->v.preferred_node;
1468         case MPOL_BIND: {
1469                 int i;
1470                 for (i = 0; a->v.zonelist->_zonerefs[i].zone; i++) {
1471                         struct zone *za, *zb;
1472                         za = zonelist_zone(&a->v.zonelist->_zonerefs[i]);
1473                         zb = zonelist_zone(&b->v.zonelist->_zonerefs[i]);
1474                         if (za != zb)
1475                                 return 0;
1476                 }
1477                 return b->v.zonelist->_zonerefs[i].zone == NULL;
1478         }
1479         default:
1480                 BUG();
1481                 return 0;
1482         }
1483 }
1484
1485 /* Slow path of a mpol destructor. */
1486 void __mpol_free(struct mempolicy *p)
1487 {
1488         if (!atomic_dec_and_test(&p->refcnt))
1489                 return;
1490         if (p->policy == MPOL_BIND)
1491                 kfree(p->v.zonelist);
1492         p->policy = MPOL_DEFAULT;
1493         kmem_cache_free(policy_cache, p);
1494 }
1495
1496 /*
1497  * Shared memory backing store policy support.
1498  *
1499  * Remember policies even when nobody has shared memory mapped.
1500  * The policies are kept in Red-Black tree linked from the inode.
1501  * They are protected by the sp->lock spinlock, which should be held
1502  * for any accesses to the tree.
1503  */
1504
1505 /* lookup first element intersecting start-end */
1506 /* Caller holds sp->lock */
1507 static struct sp_node *
1508 sp_lookup(struct shared_policy *sp, unsigned long start, unsigned long end)
1509 {
1510         struct rb_node *n = sp->root.rb_node;
1511
1512         while (n) {
1513                 struct sp_node *p = rb_entry(n, struct sp_node, nd);
1514
1515                 if (start >= p->end)
1516                         n = n->rb_right;
1517                 else if (end <= p->start)
1518                         n = n->rb_left;
1519                 else
1520                         break;
1521         }
1522         if (!n)
1523                 return NULL;
1524         for (;;) {
1525                 struct sp_node *w = NULL;
1526                 struct rb_node *prev = rb_prev(n);
1527                 if (!prev)
1528                         break;
1529                 w = rb_entry(prev, struct sp_node, nd);
1530                 if (w->end <= start)
1531                         break;
1532                 n = prev;
1533         }
1534         return rb_entry(n, struct sp_node, nd);
1535 }
1536
1537 /* Insert a new shared policy into the list. */
1538 /* Caller holds sp->lock */
1539 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
1540 {
1541         struct rb_node **p = &sp->root.rb_node;
1542         struct rb_node *parent = NULL;
1543         struct sp_node *nd;
1544
1545         while (*p) {
1546                 parent = *p;
1547                 nd = rb_entry(parent, struct sp_node, nd);
1548                 if (new->start < nd->start)
1549                         p = &(*p)->rb_left;
1550                 else if (new->end > nd->end)
1551                         p = &(*p)->rb_right;
1552                 else
1553                         BUG();
1554         }
1555         rb_link_node(&new->nd, parent, p);
1556         rb_insert_color(&new->nd, &sp->root);
1557         pr_debug("inserting %lx-%lx: %d\n", new->start, new->end,
1558                  new->policy ? new->policy->policy : 0);
1559 }
1560
1561 /* Find shared policy intersecting idx */
1562 struct mempolicy *
1563 mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
1564 {
1565         struct mempolicy *pol = NULL;
1566         struct sp_node *sn;
1567
1568         if (!sp->root.rb_node)
1569                 return NULL;
1570         spin_lock(&sp->lock);
1571         sn = sp_lookup(sp, idx, idx+1);
1572         if (sn) {
1573                 mpol_get(sn->policy);
1574                 pol = sn->policy;
1575         }
1576         spin_unlock(&sp->lock);
1577         return pol;
1578 }
1579
1580 static void sp_delete(struct shared_policy *sp, struct sp_node *n)
1581 {
1582         pr_debug("deleting %lx-l%lx\n", n->start, n->end);
1583         rb_erase(&n->nd, &sp->root);
1584         mpol_free(n->policy);
1585         kmem_cache_free(sn_cache, n);
1586 }
1587
1588 static struct sp_node *sp_alloc(unsigned long start, unsigned long end,
1589                                 struct mempolicy *pol)
1590 {
1591         struct sp_node *n = kmem_cache_alloc(sn_cache, GFP_KERNEL);
1592
1593         if (!n)
1594                 return NULL;
1595         n->start = start;
1596         n->end = end;
1597         mpol_get(pol);
1598         n->policy = pol;
1599         return n;
1600 }
1601
1602 /* Replace a policy range. */
1603 static int shared_policy_replace(struct shared_policy *sp, unsigned long start,
1604                                  unsigned long end, struct sp_node *new)
1605 {
1606         struct sp_node *n, *new2 = NULL;
1607
1608 restart:
1609         spin_lock(&sp->lock);
1610         n = sp_lookup(sp, start, end);
1611         /* Take care of old policies in the same range. */
1612         while (n && n->start < end) {
1613                 struct rb_node *next = rb_next(&n->nd);
1614                 if (n->start >= start) {
1615                         if (n->end <= end)
1616                                 sp_delete(sp, n);
1617                         else
1618                                 n->start = end;
1619                 } else {
1620                         /* Old policy spanning whole new range. */
1621                         if (n->end > end) {
1622                                 if (!new2) {
1623                                         spin_unlock(&sp->lock);
1624                                         new2 = sp_alloc(end, n->end, n->policy);
1625                                         if (!new2)
1626                                                 return -ENOMEM;
1627                                         goto restart;
1628                                 }
1629                                 n->end = start;
1630                                 sp_insert(sp, new2);
1631                                 new2 = NULL;
1632                                 break;
1633                         } else
1634                                 n->end = start;
1635                 }
1636                 if (!next)
1637                         break;
1638                 n = rb_entry(next, struct sp_node, nd);
1639         }
1640         if (new)
1641                 sp_insert(sp, new);
1642         spin_unlock(&sp->lock);
1643         if (new2) {
1644                 mpol_free(new2->policy);
1645                 kmem_cache_free(sn_cache, new2);
1646         }
1647         return 0;
1648 }
1649
1650 void mpol_shared_policy_init(struct shared_policy *info, int policy,
1651                                 nodemask_t *policy_nodes)
1652 {
1653         info->root = RB_ROOT;
1654         spin_lock_init(&info->lock);
1655
1656         if (policy != MPOL_DEFAULT) {
1657                 struct mempolicy *newpol;
1658
1659                 /* Falls back to MPOL_DEFAULT on any error */
1660                 newpol = mpol_new(policy, policy_nodes);
1661                 if (!IS_ERR(newpol)) {
1662                         /* Create pseudo-vma that contains just the policy */
1663                         struct vm_area_struct pvma;
1664
1665                         memset(&pvma, 0, sizeof(struct vm_area_struct));
1666                         /* Policy covers entire file */
1667                         pvma.vm_end = TASK_SIZE;
1668                         mpol_set_shared_policy(info, &pvma, newpol);
1669                         mpol_free(newpol);
1670                 }
1671         }
1672 }
1673
1674 int mpol_set_shared_policy(struct shared_policy *info,
1675                         struct vm_area_struct *vma, struct mempolicy *npol)
1676 {
1677         int err;
1678         struct sp_node *new = NULL;
1679         unsigned long sz = vma_pages(vma);
1680
1681         pr_debug("set_shared_policy %lx sz %lu %d %lx\n",
1682                  vma->vm_pgoff,
1683                  sz, npol? npol->policy : -1,
1684                  npol ? nodes_addr(npol->v.nodes)[0] : -1);
1685
1686         if (npol) {
1687                 new = sp_alloc(vma->vm_pgoff, vma->vm_pgoff + sz, npol);
1688                 if (!new)
1689                         return -ENOMEM;
1690         }
1691         err = shared_policy_replace(info, vma->vm_pgoff, vma->vm_pgoff+sz, new);
1692         if (err && new)
1693                 kmem_cache_free(sn_cache, new);
1694         return err;
1695 }
1696
1697 /* Free a backing policy store on inode delete. */
1698 void mpol_free_shared_policy(struct shared_policy *p)
1699 {
1700         struct sp_node *n;
1701         struct rb_node *next;
1702
1703         if (!p->root.rb_node)
1704                 return;
1705         spin_lock(&p->lock);
1706         next = rb_first(&p->root);
1707         while (next) {
1708                 n = rb_entry(next, struct sp_node, nd);
1709                 next = rb_next(&n->nd);
1710                 rb_erase(&n->nd, &p->root);
1711                 mpol_free(n->policy);
1712                 kmem_cache_free(sn_cache, n);
1713         }
1714         spin_unlock(&p->lock);
1715 }
1716
1717 /* assumes fs == KERNEL_DS */
1718 void __init numa_policy_init(void)
1719 {
1720         nodemask_t interleave_nodes;
1721         unsigned long largest = 0;
1722         int nid, prefer = 0;
1723
1724         policy_cache = kmem_cache_create("numa_policy",
1725                                          sizeof(struct mempolicy),
1726                                          0, SLAB_PANIC, NULL);
1727
1728         sn_cache = kmem_cache_create("shared_policy_node",
1729                                      sizeof(struct sp_node),
1730                                      0, SLAB_PANIC, NULL);
1731
1732         /*
1733          * Set interleaving policy for system init. Interleaving is only
1734          * enabled across suitably sized nodes (default is >= 16MB), or
1735          * fall back to the largest node if they're all smaller.
1736          */
1737         nodes_clear(interleave_nodes);
1738         for_each_node_state(nid, N_HIGH_MEMORY) {
1739                 unsigned long total_pages = node_present_pages(nid);
1740
1741                 /* Preserve the largest node */
1742                 if (largest < total_pages) {
1743                         largest = total_pages;
1744                         prefer = nid;
1745                 }
1746
1747                 /* Interleave this node? */
1748                 if ((total_pages << PAGE_SHIFT) >= (16 << 20))
1749                         node_set(nid, interleave_nodes);
1750         }
1751
1752         /* All too small, use the largest */
1753         if (unlikely(nodes_empty(interleave_nodes)))
1754                 node_set(prefer, interleave_nodes);
1755
1756         if (do_set_mempolicy(MPOL_INTERLEAVE, &interleave_nodes))
1757                 printk("numa_policy_init: interleaving failed\n");
1758 }
1759
1760 /* Reset policy of current process to default */
1761 void numa_default_policy(void)
1762 {
1763         do_set_mempolicy(MPOL_DEFAULT, NULL);
1764 }
1765
1766 /* Migrate a policy to a different set of nodes */
1767 static void mpol_rebind_policy(struct mempolicy *pol,
1768                                const nodemask_t *newmask)
1769 {
1770         nodemask_t *mpolmask;
1771         nodemask_t tmp;
1772
1773         if (!pol)
1774                 return;
1775         mpolmask = &pol->cpuset_mems_allowed;
1776         if (nodes_equal(*mpolmask, *newmask))
1777                 return;
1778
1779         switch (pol->policy) {
1780         case MPOL_DEFAULT:
1781                 break;
1782         case MPOL_INTERLEAVE:
1783                 nodes_remap(tmp, pol->v.nodes, *mpolmask, *newmask);
1784                 pol->v.nodes = tmp;
1785                 *mpolmask = *newmask;
1786                 current->il_next = node_remap(current->il_next,
1787                                                 *mpolmask, *newmask);
1788                 break;
1789         case MPOL_PREFERRED:
1790                 pol->v.preferred_node = node_remap(pol->v.preferred_node,
1791                                                 *mpolmask, *newmask);
1792                 *mpolmask = *newmask;
1793                 break;
1794         case MPOL_BIND: {
1795                 nodemask_t nodes;
1796                 struct zoneref *z;
1797                 struct zonelist *zonelist;
1798
1799                 nodes_clear(nodes);
1800                 for (z = pol->v.zonelist->_zonerefs; z->zone; z++)
1801                         node_set(zonelist_node_idx(z), nodes);
1802                 nodes_remap(tmp, nodes, *mpolmask, *newmask);
1803                 nodes = tmp;
1804
1805                 zonelist = bind_zonelist(&nodes);
1806
1807                 /* If no mem, then zonelist is NULL and we keep old zonelist.
1808                  * If that old zonelist has no remaining mems_allowed nodes,
1809                  * then zonelist_policy() will "FALL THROUGH" to MPOL_DEFAULT.
1810                  */
1811
1812                 if (!IS_ERR(zonelist)) {
1813                         /* Good - got mem - substitute new zonelist */
1814                         kfree(pol->v.zonelist);
1815                         pol->v.zonelist = zonelist;
1816                 }
1817                 *mpolmask = *newmask;
1818                 break;
1819         }
1820         default:
1821                 BUG();
1822                 break;
1823         }
1824 }
1825
1826 /*
1827  * Wrapper for mpol_rebind_policy() that just requires task
1828  * pointer, and updates task mempolicy.
1829  */
1830
1831 void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new)
1832 {
1833         mpol_rebind_policy(tsk->mempolicy, new);
1834 }
1835
1836 /*
1837  * Rebind each vma in mm to new nodemask.
1838  *
1839  * Call holding a reference to mm.  Takes mm->mmap_sem during call.
1840  */
1841
1842 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
1843 {
1844         struct vm_area_struct *vma;
1845
1846         down_write(&mm->mmap_sem);
1847         for (vma = mm->mmap; vma; vma = vma->vm_next)
1848                 mpol_rebind_policy(vma->vm_policy, new);
1849         up_write(&mm->mmap_sem);
1850 }
1851
1852 /*
1853  * Display pages allocated per node and memory policy via /proc.
1854  */
1855
1856 static const char * const policy_types[] =
1857         { "default", "prefer", "bind", "interleave" };
1858
1859 /*
1860  * Convert a mempolicy into a string.
1861  * Returns the number of characters in buffer (if positive)
1862  * or an error (negative)
1863  */
1864 static inline int mpol_to_str(char *buffer, int maxlen, struct mempolicy *pol)
1865 {
1866         char *p = buffer;
1867         int l;
1868         nodemask_t nodes;
1869         int mode = pol ? pol->policy : MPOL_DEFAULT;
1870
1871         switch (mode) {
1872         case MPOL_DEFAULT:
1873                 nodes_clear(nodes);
1874                 break;
1875
1876         case MPOL_PREFERRED:
1877                 nodes_clear(nodes);
1878                 node_set(pol->v.preferred_node, nodes);
1879                 break;
1880
1881         case MPOL_BIND:
1882                 get_zonemask(pol, &nodes);
1883                 break;
1884
1885         case MPOL_INTERLEAVE:
1886                 nodes = pol->v.nodes;
1887                 break;
1888
1889         default:
1890                 BUG();
1891                 return -EFAULT;
1892         }
1893
1894         l = strlen(policy_types[mode]);
1895         if (buffer + maxlen < p + l + 1)
1896                 return -ENOSPC;
1897
1898         strcpy(p, policy_types[mode]);
1899         p += l;
1900
1901         if (!nodes_empty(nodes)) {
1902                 if (buffer + maxlen < p + 2)
1903                         return -ENOSPC;
1904                 *p++ = '=';
1905                 p += nodelist_scnprintf(p, buffer + maxlen - p, nodes);
1906         }
1907         return p - buffer;
1908 }
1909
1910 struct numa_maps {
1911         unsigned long pages;
1912         unsigned long anon;
1913         unsigned long active;
1914         unsigned long writeback;
1915         unsigned long mapcount_max;
1916         unsigned long dirty;
1917         unsigned long swapcache;
1918         unsigned long node[MAX_NUMNODES];
1919 };
1920
1921 static void gather_stats(struct page *page, void *private, int pte_dirty)
1922 {
1923         struct numa_maps *md = private;
1924         int count = page_mapcount(page);
1925
1926         md->pages++;
1927         if (pte_dirty || PageDirty(page))
1928                 md->dirty++;
1929
1930         if (PageSwapCache(page))
1931                 md->swapcache++;
1932
1933         if (PageActive(page))
1934                 md->active++;
1935
1936         if (PageWriteback(page))
1937                 md->writeback++;
1938
1939         if (PageAnon(page))
1940                 md->anon++;
1941
1942         if (count > md->mapcount_max)
1943                 md->mapcount_max = count;
1944
1945         md->node[page_to_nid(page)]++;
1946 }
1947
1948 #ifdef CONFIG_HUGETLB_PAGE
1949 static void check_huge_range(struct vm_area_struct *vma,
1950                 unsigned long start, unsigned long end,
1951                 struct numa_maps *md)
1952 {
1953         unsigned long addr;
1954         struct page *page;
1955
1956         for (addr = start; addr < end; addr += HPAGE_SIZE) {
1957                 pte_t *ptep = huge_pte_offset(vma->vm_mm, addr & HPAGE_MASK);
1958                 pte_t pte;
1959
1960                 if (!ptep)
1961                         continue;
1962
1963                 pte = *ptep;
1964                 if (pte_none(pte))
1965                         continue;
1966
1967                 page = pte_page(pte);
1968                 if (!page)
1969                         continue;
1970
1971                 gather_stats(page, md, pte_dirty(*ptep));
1972         }
1973 }
1974 #else
1975 static inline void check_huge_range(struct vm_area_struct *vma,
1976                 unsigned long start, unsigned long end,
1977                 struct numa_maps *md)
1978 {
1979 }
1980 #endif
1981
1982 int show_numa_map(struct seq_file *m, void *v)
1983 {
1984         struct proc_maps_private *priv = m->private;
1985         struct vm_area_struct *vma = v;
1986         struct numa_maps *md;
1987         struct file *file = vma->vm_file;
1988         struct mm_struct *mm = vma->vm_mm;
1989         struct mempolicy *pol;
1990         int n;
1991         char buffer[50];
1992
1993         if (!mm)
1994                 return 0;
1995
1996         md = kzalloc(sizeof(struct numa_maps), GFP_KERNEL);
1997         if (!md)
1998                 return 0;
1999
2000         pol = get_vma_policy(priv->task, vma, vma->vm_start);
2001         mpol_to_str(buffer, sizeof(buffer), pol);
2002         /*
2003          * unref shared or other task's mempolicy
2004          */
2005         if (pol != &default_policy && pol != current->mempolicy)
2006                 __mpol_free(pol);
2007
2008         seq_printf(m, "%08lx %s", vma->vm_start, buffer);
2009
2010         if (file) {
2011                 seq_printf(m, " file=");
2012                 seq_path(m, &file->f_path, "\n\t= ");
2013         } else if (vma->vm_start <= mm->brk && vma->vm_end >= mm->start_brk) {
2014                 seq_printf(m, " heap");
2015         } else if (vma->vm_start <= mm->start_stack &&
2016                         vma->vm_end >= mm->start_stack) {
2017                 seq_printf(m, " stack");
2018         }
2019
2020         if (is_vm_hugetlb_page(vma)) {
2021                 check_huge_range(vma, vma->vm_start, vma->vm_end, md);
2022                 seq_printf(m, " huge");
2023         } else {
2024                 check_pgd_range(vma, vma->vm_start, vma->vm_end,
2025                         &node_states[N_HIGH_MEMORY], MPOL_MF_STATS, md);
2026         }
2027
2028         if (!md->pages)
2029                 goto out;
2030
2031         if (md->anon)
2032                 seq_printf(m," anon=%lu",md->anon);
2033
2034         if (md->dirty)
2035                 seq_printf(m," dirty=%lu",md->dirty);
2036
2037         if (md->pages != md->anon && md->pages != md->dirty)
2038                 seq_printf(m, " mapped=%lu", md->pages);
2039
2040         if (md->mapcount_max > 1)
2041                 seq_printf(m, " mapmax=%lu", md->mapcount_max);
2042
2043         if (md->swapcache)
2044                 seq_printf(m," swapcache=%lu", md->swapcache);
2045
2046         if (md->active < md->pages && !is_vm_hugetlb_page(vma))
2047                 seq_printf(m," active=%lu", md->active);
2048
2049         if (md->writeback)
2050                 seq_printf(m," writeback=%lu", md->writeback);
2051
2052         for_each_node_state(n, N_HIGH_MEMORY)
2053                 if (md->node[n])
2054                         seq_printf(m, " N%d=%lu", n, md->node[n]);
2055 out:
2056         seq_putc(m, '\n');
2057         kfree(md);
2058
2059         if (m->count < m->size)
2060                 m->version = (vma != priv->tail_vma) ? vma->vm_start : 0;
2061         return 0;
2062 }