mm: compaction: fix COMPACTPAGEFAILED counting
[linux-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 */
67
68 #include <linux/mempolicy.h>
69 #include <linux/mm.h>
70 #include <linux/highmem.h>
71 #include <linux/hugetlb.h>
72 #include <linux/kernel.h>
73 #include <linux/sched.h>
74 #include <linux/nodemask.h>
75 #include <linux/cpuset.h>
76 #include <linux/slab.h>
77 #include <linux/string.h>
78 #include <linux/module.h>
79 #include <linux/nsproxy.h>
80 #include <linux/interrupt.h>
81 #include <linux/init.h>
82 #include <linux/compat.h>
83 #include <linux/swap.h>
84 #include <linux/seq_file.h>
85 #include <linux/proc_fs.h>
86 #include <linux/migrate.h>
87 #include <linux/ksm.h>
88 #include <linux/rmap.h>
89 #include <linux/security.h>
90 #include <linux/syscalls.h>
91 #include <linux/ctype.h>
92 #include <linux/mm_inline.h>
93
94 #include <asm/tlbflush.h>
95 #include <asm/uaccess.h>
96
97 #include "internal.h"
98
99 /* Internal flags */
100 #define MPOL_MF_DISCONTIG_OK (MPOL_MF_INTERNAL << 0)    /* Skip checks for continuous vmas */
101 #define MPOL_MF_INVERT (MPOL_MF_INTERNAL << 1)          /* Invert check for nodemask */
102 #define MPOL_MF_STATS (MPOL_MF_INTERNAL << 2)           /* Gather statistics */
103
104 static struct kmem_cache *policy_cache;
105 static struct kmem_cache *sn_cache;
106
107 /* Highest zone. An specific allocation for a zone below that is not
108    policied. */
109 enum zone_type policy_zone = 0;
110
111 /*
112  * run-time system-wide default policy => local allocation
113  */
114 struct mempolicy default_policy = {
115         .refcnt = ATOMIC_INIT(1), /* never free it */
116         .mode = MPOL_PREFERRED,
117         .flags = MPOL_F_LOCAL,
118 };
119
120 static const struct mempolicy_operations {
121         int (*create)(struct mempolicy *pol, const nodemask_t *nodes);
122         /*
123          * If read-side task has no lock to protect task->mempolicy, write-side
124          * task will rebind the task->mempolicy by two step. The first step is
125          * setting all the newly nodes, and the second step is cleaning all the
126          * disallowed nodes. In this way, we can avoid finding no node to alloc
127          * page.
128          * If we have a lock to protect task->mempolicy in read-side, we do
129          * rebind directly.
130          *
131          * step:
132          *      MPOL_REBIND_ONCE - do rebind work at once
133          *      MPOL_REBIND_STEP1 - set all the newly nodes
134          *      MPOL_REBIND_STEP2 - clean all the disallowed nodes
135          */
136         void (*rebind)(struct mempolicy *pol, const nodemask_t *nodes,
137                         enum mpol_rebind_step step);
138 } mpol_ops[MPOL_MAX];
139
140 /* Check that the nodemask contains at least one populated zone */
141 static int is_valid_nodemask(const nodemask_t *nodemask)
142 {
143         int nd, k;
144
145         for_each_node_mask(nd, *nodemask) {
146                 struct zone *z;
147
148                 for (k = 0; k <= policy_zone; k++) {
149                         z = &NODE_DATA(nd)->node_zones[k];
150                         if (z->present_pages > 0)
151                                 return 1;
152                 }
153         }
154
155         return 0;
156 }
157
158 static inline int mpol_store_user_nodemask(const struct mempolicy *pol)
159 {
160         return pol->flags & MPOL_MODE_FLAGS;
161 }
162
163 static void mpol_relative_nodemask(nodemask_t *ret, const nodemask_t *orig,
164                                    const nodemask_t *rel)
165 {
166         nodemask_t tmp;
167         nodes_fold(tmp, *orig, nodes_weight(*rel));
168         nodes_onto(*ret, tmp, *rel);
169 }
170
171 static int mpol_new_interleave(struct mempolicy *pol, const nodemask_t *nodes)
172 {
173         if (nodes_empty(*nodes))
174                 return -EINVAL;
175         pol->v.nodes = *nodes;
176         return 0;
177 }
178
179 static int mpol_new_preferred(struct mempolicy *pol, const nodemask_t *nodes)
180 {
181         if (!nodes)
182                 pol->flags |= MPOL_F_LOCAL;     /* local allocation */
183         else if (nodes_empty(*nodes))
184                 return -EINVAL;                 /*  no allowed nodes */
185         else
186                 pol->v.preferred_node = first_node(*nodes);
187         return 0;
188 }
189
190 static int mpol_new_bind(struct mempolicy *pol, const nodemask_t *nodes)
191 {
192         if (!is_valid_nodemask(nodes))
193                 return -EINVAL;
194         pol->v.nodes = *nodes;
195         return 0;
196 }
197
198 /*
199  * mpol_set_nodemask is called after mpol_new() to set up the nodemask, if
200  * any, for the new policy.  mpol_new() has already validated the nodes
201  * parameter with respect to the policy mode and flags.  But, we need to
202  * handle an empty nodemask with MPOL_PREFERRED here.
203  *
204  * Must be called holding task's alloc_lock to protect task's mems_allowed
205  * and mempolicy.  May also be called holding the mmap_semaphore for write.
206  */
207 static int mpol_set_nodemask(struct mempolicy *pol,
208                      const nodemask_t *nodes, struct nodemask_scratch *nsc)
209 {
210         int ret;
211
212         /* if mode is MPOL_DEFAULT, pol is NULL. This is right. */
213         if (pol == NULL)
214                 return 0;
215         /* Check N_HIGH_MEMORY */
216         nodes_and(nsc->mask1,
217                   cpuset_current_mems_allowed, node_states[N_HIGH_MEMORY]);
218
219         VM_BUG_ON(!nodes);
220         if (pol->mode == MPOL_PREFERRED && nodes_empty(*nodes))
221                 nodes = NULL;   /* explicit local allocation */
222         else {
223                 if (pol->flags & MPOL_F_RELATIVE_NODES)
224                         mpol_relative_nodemask(&nsc->mask2, nodes,&nsc->mask1);
225                 else
226                         nodes_and(nsc->mask2, *nodes, nsc->mask1);
227
228                 if (mpol_store_user_nodemask(pol))
229                         pol->w.user_nodemask = *nodes;
230                 else
231                         pol->w.cpuset_mems_allowed =
232                                                 cpuset_current_mems_allowed;
233         }
234
235         if (nodes)
236                 ret = mpol_ops[pol->mode].create(pol, &nsc->mask2);
237         else
238                 ret = mpol_ops[pol->mode].create(pol, NULL);
239         return ret;
240 }
241
242 /*
243  * This function just creates a new policy, does some check and simple
244  * initialization. You must invoke mpol_set_nodemask() to set nodes.
245  */
246 static struct mempolicy *mpol_new(unsigned short mode, unsigned short flags,
247                                   nodemask_t *nodes)
248 {
249         struct mempolicy *policy;
250
251         pr_debug("setting mode %d flags %d nodes[0] %lx\n",
252                  mode, flags, nodes ? nodes_addr(*nodes)[0] : -1);
253
254         if (mode == MPOL_DEFAULT) {
255                 if (nodes && !nodes_empty(*nodes))
256                         return ERR_PTR(-EINVAL);
257                 return NULL;    /* simply delete any existing policy */
258         }
259         VM_BUG_ON(!nodes);
260
261         /*
262          * MPOL_PREFERRED cannot be used with MPOL_F_STATIC_NODES or
263          * MPOL_F_RELATIVE_NODES if the nodemask is empty (local allocation).
264          * All other modes require a valid pointer to a non-empty nodemask.
265          */
266         if (mode == MPOL_PREFERRED) {
267                 if (nodes_empty(*nodes)) {
268                         if (((flags & MPOL_F_STATIC_NODES) ||
269                              (flags & MPOL_F_RELATIVE_NODES)))
270                                 return ERR_PTR(-EINVAL);
271                 }
272         } else if (nodes_empty(*nodes))
273                 return ERR_PTR(-EINVAL);
274         policy = kmem_cache_alloc(policy_cache, GFP_KERNEL);
275         if (!policy)
276                 return ERR_PTR(-ENOMEM);
277         atomic_set(&policy->refcnt, 1);
278         policy->mode = mode;
279         policy->flags = flags;
280
281         return policy;
282 }
283
284 /* Slow path of a mpol destructor. */
285 void __mpol_put(struct mempolicy *p)
286 {
287         if (!atomic_dec_and_test(&p->refcnt))
288                 return;
289         kmem_cache_free(policy_cache, p);
290 }
291
292 static void mpol_rebind_default(struct mempolicy *pol, const nodemask_t *nodes,
293                                 enum mpol_rebind_step step)
294 {
295 }
296
297 /*
298  * step:
299  *      MPOL_REBIND_ONCE  - do rebind work at once
300  *      MPOL_REBIND_STEP1 - set all the newly nodes
301  *      MPOL_REBIND_STEP2 - clean all the disallowed nodes
302  */
303 static void mpol_rebind_nodemask(struct mempolicy *pol, const nodemask_t *nodes,
304                                  enum mpol_rebind_step step)
305 {
306         nodemask_t tmp;
307
308         if (pol->flags & MPOL_F_STATIC_NODES)
309                 nodes_and(tmp, pol->w.user_nodemask, *nodes);
310         else if (pol->flags & MPOL_F_RELATIVE_NODES)
311                 mpol_relative_nodemask(&tmp, &pol->w.user_nodemask, nodes);
312         else {
313                 /*
314                  * if step == 1, we use ->w.cpuset_mems_allowed to cache the
315                  * result
316                  */
317                 if (step == MPOL_REBIND_ONCE || step == MPOL_REBIND_STEP1) {
318                         nodes_remap(tmp, pol->v.nodes,
319                                         pol->w.cpuset_mems_allowed, *nodes);
320                         pol->w.cpuset_mems_allowed = step ? tmp : *nodes;
321                 } else if (step == MPOL_REBIND_STEP2) {
322                         tmp = pol->w.cpuset_mems_allowed;
323                         pol->w.cpuset_mems_allowed = *nodes;
324                 } else
325                         BUG();
326         }
327
328         if (nodes_empty(tmp))
329                 tmp = *nodes;
330
331         if (step == MPOL_REBIND_STEP1)
332                 nodes_or(pol->v.nodes, pol->v.nodes, tmp);
333         else if (step == MPOL_REBIND_ONCE || step == MPOL_REBIND_STEP2)
334                 pol->v.nodes = tmp;
335         else
336                 BUG();
337
338         if (!node_isset(current->il_next, tmp)) {
339                 current->il_next = next_node(current->il_next, tmp);
340                 if (current->il_next >= MAX_NUMNODES)
341                         current->il_next = first_node(tmp);
342                 if (current->il_next >= MAX_NUMNODES)
343                         current->il_next = numa_node_id();
344         }
345 }
346
347 static void mpol_rebind_preferred(struct mempolicy *pol,
348                                   const nodemask_t *nodes,
349                                   enum mpol_rebind_step step)
350 {
351         nodemask_t tmp;
352
353         if (pol->flags & MPOL_F_STATIC_NODES) {
354                 int node = first_node(pol->w.user_nodemask);
355
356                 if (node_isset(node, *nodes)) {
357                         pol->v.preferred_node = node;
358                         pol->flags &= ~MPOL_F_LOCAL;
359                 } else
360                         pol->flags |= MPOL_F_LOCAL;
361         } else if (pol->flags & MPOL_F_RELATIVE_NODES) {
362                 mpol_relative_nodemask(&tmp, &pol->w.user_nodemask, nodes);
363                 pol->v.preferred_node = first_node(tmp);
364         } else if (!(pol->flags & MPOL_F_LOCAL)) {
365                 pol->v.preferred_node = node_remap(pol->v.preferred_node,
366                                                    pol->w.cpuset_mems_allowed,
367                                                    *nodes);
368                 pol->w.cpuset_mems_allowed = *nodes;
369         }
370 }
371
372 /*
373  * mpol_rebind_policy - Migrate a policy to a different set of nodes
374  *
375  * If read-side task has no lock to protect task->mempolicy, write-side
376  * task will rebind the task->mempolicy by two step. The first step is
377  * setting all the newly nodes, and the second step is cleaning all the
378  * disallowed nodes. In this way, we can avoid finding no node to alloc
379  * page.
380  * If we have a lock to protect task->mempolicy in read-side, we do
381  * rebind directly.
382  *
383  * step:
384  *      MPOL_REBIND_ONCE  - do rebind work at once
385  *      MPOL_REBIND_STEP1 - set all the newly nodes
386  *      MPOL_REBIND_STEP2 - clean all the disallowed nodes
387  */
388 static void mpol_rebind_policy(struct mempolicy *pol, const nodemask_t *newmask,
389                                 enum mpol_rebind_step step)
390 {
391         if (!pol)
392                 return;
393         if (!mpol_store_user_nodemask(pol) && step == 0 &&
394             nodes_equal(pol->w.cpuset_mems_allowed, *newmask))
395                 return;
396
397         if (step == MPOL_REBIND_STEP1 && (pol->flags & MPOL_F_REBINDING))
398                 return;
399
400         if (step == MPOL_REBIND_STEP2 && !(pol->flags & MPOL_F_REBINDING))
401                 BUG();
402
403         if (step == MPOL_REBIND_STEP1)
404                 pol->flags |= MPOL_F_REBINDING;
405         else if (step == MPOL_REBIND_STEP2)
406                 pol->flags &= ~MPOL_F_REBINDING;
407         else if (step >= MPOL_REBIND_NSTEP)
408                 BUG();
409
410         mpol_ops[pol->mode].rebind(pol, newmask, step);
411 }
412
413 /*
414  * Wrapper for mpol_rebind_policy() that just requires task
415  * pointer, and updates task mempolicy.
416  *
417  * Called with task's alloc_lock held.
418  */
419
420 void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new,
421                         enum mpol_rebind_step step)
422 {
423         mpol_rebind_policy(tsk->mempolicy, new, step);
424 }
425
426 /*
427  * Rebind each vma in mm to new nodemask.
428  *
429  * Call holding a reference to mm.  Takes mm->mmap_sem during call.
430  */
431
432 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
433 {
434         struct vm_area_struct *vma;
435
436         down_write(&mm->mmap_sem);
437         for (vma = mm->mmap; vma; vma = vma->vm_next)
438                 mpol_rebind_policy(vma->vm_policy, new, MPOL_REBIND_ONCE);
439         up_write(&mm->mmap_sem);
440 }
441
442 static const struct mempolicy_operations mpol_ops[MPOL_MAX] = {
443         [MPOL_DEFAULT] = {
444                 .rebind = mpol_rebind_default,
445         },
446         [MPOL_INTERLEAVE] = {
447                 .create = mpol_new_interleave,
448                 .rebind = mpol_rebind_nodemask,
449         },
450         [MPOL_PREFERRED] = {
451                 .create = mpol_new_preferred,
452                 .rebind = mpol_rebind_preferred,
453         },
454         [MPOL_BIND] = {
455                 .create = mpol_new_bind,
456                 .rebind = mpol_rebind_nodemask,
457         },
458 };
459
460 static void gather_stats(struct page *, void *, int pte_dirty);
461 static void migrate_page_add(struct page *page, struct list_head *pagelist,
462                                 unsigned long flags);
463
464 /* Scan through pages checking if pages follow certain conditions. */
465 static int check_pte_range(struct vm_area_struct *vma, pmd_t *pmd,
466                 unsigned long addr, unsigned long end,
467                 const nodemask_t *nodes, unsigned long flags,
468                 void *private)
469 {
470         pte_t *orig_pte;
471         pte_t *pte;
472         spinlock_t *ptl;
473
474         orig_pte = pte = pte_offset_map_lock(vma->vm_mm, pmd, addr, &ptl);
475         do {
476                 struct page *page;
477                 int nid;
478
479                 if (!pte_present(*pte))
480                         continue;
481                 page = vm_normal_page(vma, addr, *pte);
482                 if (!page)
483                         continue;
484                 /*
485                  * vm_normal_page() filters out zero pages, but there might
486                  * still be PageReserved pages to skip, perhaps in a VDSO.
487                  * And we cannot move PageKsm pages sensibly or safely yet.
488                  */
489                 if (PageReserved(page) || PageKsm(page))
490                         continue;
491                 nid = page_to_nid(page);
492                 if (node_isset(nid, *nodes) == !!(flags & MPOL_MF_INVERT))
493                         continue;
494
495                 if (flags & MPOL_MF_STATS)
496                         gather_stats(page, private, pte_dirty(*pte));
497                 else if (flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL))
498                         migrate_page_add(page, private, flags);
499                 else
500                         break;
501         } while (pte++, addr += PAGE_SIZE, addr != end);
502         pte_unmap_unlock(orig_pte, ptl);
503         return addr != end;
504 }
505
506 static inline int check_pmd_range(struct vm_area_struct *vma, pud_t *pud,
507                 unsigned long addr, unsigned long end,
508                 const nodemask_t *nodes, unsigned long flags,
509                 void *private)
510 {
511         pmd_t *pmd;
512         unsigned long next;
513
514         pmd = pmd_offset(pud, addr);
515         do {
516                 next = pmd_addr_end(addr, end);
517                 if (pmd_none_or_clear_bad(pmd))
518                         continue;
519                 if (check_pte_range(vma, pmd, addr, next, nodes,
520                                     flags, private))
521                         return -EIO;
522         } while (pmd++, addr = next, addr != end);
523         return 0;
524 }
525
526 static inline int check_pud_range(struct vm_area_struct *vma, pgd_t *pgd,
527                 unsigned long addr, unsigned long end,
528                 const nodemask_t *nodes, unsigned long flags,
529                 void *private)
530 {
531         pud_t *pud;
532         unsigned long next;
533
534         pud = pud_offset(pgd, addr);
535         do {
536                 next = pud_addr_end(addr, end);
537                 if (pud_none_or_clear_bad(pud))
538                         continue;
539                 if (check_pmd_range(vma, pud, addr, next, nodes,
540                                     flags, private))
541                         return -EIO;
542         } while (pud++, addr = next, addr != end);
543         return 0;
544 }
545
546 static inline int check_pgd_range(struct vm_area_struct *vma,
547                 unsigned long addr, unsigned long end,
548                 const nodemask_t *nodes, unsigned long flags,
549                 void *private)
550 {
551         pgd_t *pgd;
552         unsigned long next;
553
554         pgd = pgd_offset(vma->vm_mm, addr);
555         do {
556                 next = pgd_addr_end(addr, end);
557                 if (pgd_none_or_clear_bad(pgd))
558                         continue;
559                 if (check_pud_range(vma, pgd, addr, next, nodes,
560                                     flags, private))
561                         return -EIO;
562         } while (pgd++, addr = next, addr != end);
563         return 0;
564 }
565
566 /*
567  * Check if all pages in a range are on a set of nodes.
568  * If pagelist != NULL then isolate pages from the LRU and
569  * put them on the pagelist.
570  */
571 static struct vm_area_struct *
572 check_range(struct mm_struct *mm, unsigned long start, unsigned long end,
573                 const nodemask_t *nodes, unsigned long flags, void *private)
574 {
575         int err;
576         struct vm_area_struct *first, *vma, *prev;
577
578
579         first = find_vma(mm, start);
580         if (!first)
581                 return ERR_PTR(-EFAULT);
582         prev = NULL;
583         for (vma = first; vma && vma->vm_start < end; vma = vma->vm_next) {
584                 if (!(flags & MPOL_MF_DISCONTIG_OK)) {
585                         if (!vma->vm_next && vma->vm_end < end)
586                                 return ERR_PTR(-EFAULT);
587                         if (prev && prev->vm_end < vma->vm_start)
588                                 return ERR_PTR(-EFAULT);
589                 }
590                 if (!is_vm_hugetlb_page(vma) &&
591                     ((flags & MPOL_MF_STRICT) ||
592                      ((flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)) &&
593                                 vma_migratable(vma)))) {
594                         unsigned long endvma = vma->vm_end;
595
596                         if (endvma > end)
597                                 endvma = end;
598                         if (vma->vm_start > start)
599                                 start = vma->vm_start;
600                         err = check_pgd_range(vma, start, endvma, nodes,
601                                                 flags, private);
602                         if (err) {
603                                 first = ERR_PTR(err);
604                                 break;
605                         }
606                 }
607                 prev = vma;
608         }
609         return first;
610 }
611
612 /* Apply policy to a single VMA */
613 static int policy_vma(struct vm_area_struct *vma, struct mempolicy *new)
614 {
615         int err = 0;
616         struct mempolicy *old = vma->vm_policy;
617
618         pr_debug("vma %lx-%lx/%lx vm_ops %p vm_file %p set_policy %p\n",
619                  vma->vm_start, vma->vm_end, vma->vm_pgoff,
620                  vma->vm_ops, vma->vm_file,
621                  vma->vm_ops ? vma->vm_ops->set_policy : NULL);
622
623         if (vma->vm_ops && vma->vm_ops->set_policy)
624                 err = vma->vm_ops->set_policy(vma, new);
625         if (!err) {
626                 mpol_get(new);
627                 vma->vm_policy = new;
628                 mpol_put(old);
629         }
630         return err;
631 }
632
633 /* Step 2: apply policy to a range and do splits. */
634 static int mbind_range(struct mm_struct *mm, unsigned long start,
635                        unsigned long end, struct mempolicy *new_pol)
636 {
637         struct vm_area_struct *next;
638         struct vm_area_struct *prev;
639         struct vm_area_struct *vma;
640         int err = 0;
641         pgoff_t pgoff;
642         unsigned long vmstart;
643         unsigned long vmend;
644
645         vma = find_vma_prev(mm, start, &prev);
646         if (!vma || vma->vm_start > start)
647                 return -EFAULT;
648
649         for (; vma && vma->vm_start < end; prev = vma, vma = next) {
650                 next = vma->vm_next;
651                 vmstart = max(start, vma->vm_start);
652                 vmend   = min(end, vma->vm_end);
653
654                 pgoff = vma->vm_pgoff + ((start - vma->vm_start) >> PAGE_SHIFT);
655                 prev = vma_merge(mm, prev, vmstart, vmend, vma->vm_flags,
656                                   vma->anon_vma, vma->vm_file, pgoff, new_pol);
657                 if (prev) {
658                         vma = prev;
659                         next = vma->vm_next;
660                         continue;
661                 }
662                 if (vma->vm_start != vmstart) {
663                         err = split_vma(vma->vm_mm, vma, vmstart, 1);
664                         if (err)
665                                 goto out;
666                 }
667                 if (vma->vm_end != vmend) {
668                         err = split_vma(vma->vm_mm, vma, vmend, 0);
669                         if (err)
670                                 goto out;
671                 }
672                 err = policy_vma(vma, new_pol);
673                 if (err)
674                         goto out;
675         }
676
677  out:
678         return err;
679 }
680
681 /*
682  * Update task->flags PF_MEMPOLICY bit: set iff non-default
683  * mempolicy.  Allows more rapid checking of this (combined perhaps
684  * with other PF_* flag bits) on memory allocation hot code paths.
685  *
686  * If called from outside this file, the task 'p' should -only- be
687  * a newly forked child not yet visible on the task list, because
688  * manipulating the task flags of a visible task is not safe.
689  *
690  * The above limitation is why this routine has the funny name
691  * mpol_fix_fork_child_flag().
692  *
693  * It is also safe to call this with a task pointer of current,
694  * which the static wrapper mpol_set_task_struct_flag() does,
695  * for use within this file.
696  */
697
698 void mpol_fix_fork_child_flag(struct task_struct *p)
699 {
700         if (p->mempolicy)
701                 p->flags |= PF_MEMPOLICY;
702         else
703                 p->flags &= ~PF_MEMPOLICY;
704 }
705
706 static void mpol_set_task_struct_flag(void)
707 {
708         mpol_fix_fork_child_flag(current);
709 }
710
711 /* Set the process memory policy */
712 static long do_set_mempolicy(unsigned short mode, unsigned short flags,
713                              nodemask_t *nodes)
714 {
715         struct mempolicy *new, *old;
716         struct mm_struct *mm = current->mm;
717         NODEMASK_SCRATCH(scratch);
718         int ret;
719
720         if (!scratch)
721                 return -ENOMEM;
722
723         new = mpol_new(mode, flags, nodes);
724         if (IS_ERR(new)) {
725                 ret = PTR_ERR(new);
726                 goto out;
727         }
728         /*
729          * prevent changing our mempolicy while show_numa_maps()
730          * is using it.
731          * Note:  do_set_mempolicy() can be called at init time
732          * with no 'mm'.
733          */
734         if (mm)
735                 down_write(&mm->mmap_sem);
736         task_lock(current);
737         ret = mpol_set_nodemask(new, nodes, scratch);
738         if (ret) {
739                 task_unlock(current);
740                 if (mm)
741                         up_write(&mm->mmap_sem);
742                 mpol_put(new);
743                 goto out;
744         }
745         old = current->mempolicy;
746         current->mempolicy = new;
747         mpol_set_task_struct_flag();
748         if (new && new->mode == MPOL_INTERLEAVE &&
749             nodes_weight(new->v.nodes))
750                 current->il_next = first_node(new->v.nodes);
751         task_unlock(current);
752         if (mm)
753                 up_write(&mm->mmap_sem);
754
755         mpol_put(old);
756         ret = 0;
757 out:
758         NODEMASK_SCRATCH_FREE(scratch);
759         return ret;
760 }
761
762 /*
763  * Return nodemask for policy for get_mempolicy() query
764  *
765  * Called with task's alloc_lock held
766  */
767 static void get_policy_nodemask(struct mempolicy *p, nodemask_t *nodes)
768 {
769         nodes_clear(*nodes);
770         if (p == &default_policy)
771                 return;
772
773         switch (p->mode) {
774         case MPOL_BIND:
775                 /* Fall through */
776         case MPOL_INTERLEAVE:
777                 *nodes = p->v.nodes;
778                 break;
779         case MPOL_PREFERRED:
780                 if (!(p->flags & MPOL_F_LOCAL))
781                         node_set(p->v.preferred_node, *nodes);
782                 /* else return empty node mask for local allocation */
783                 break;
784         default:
785                 BUG();
786         }
787 }
788
789 static int lookup_node(struct mm_struct *mm, unsigned long addr)
790 {
791         struct page *p;
792         int err;
793
794         err = get_user_pages(current, mm, addr & PAGE_MASK, 1, 0, 0, &p, NULL);
795         if (err >= 0) {
796                 err = page_to_nid(p);
797                 put_page(p);
798         }
799         return err;
800 }
801
802 /* Retrieve NUMA policy */
803 static long do_get_mempolicy(int *policy, nodemask_t *nmask,
804                              unsigned long addr, unsigned long flags)
805 {
806         int err;
807         struct mm_struct *mm = current->mm;
808         struct vm_area_struct *vma = NULL;
809         struct mempolicy *pol = current->mempolicy;
810
811         if (flags &
812                 ~(unsigned long)(MPOL_F_NODE|MPOL_F_ADDR|MPOL_F_MEMS_ALLOWED))
813                 return -EINVAL;
814
815         if (flags & MPOL_F_MEMS_ALLOWED) {
816                 if (flags & (MPOL_F_NODE|MPOL_F_ADDR))
817                         return -EINVAL;
818                 *policy = 0;    /* just so it's initialized */
819                 task_lock(current);
820                 *nmask  = cpuset_current_mems_allowed;
821                 task_unlock(current);
822                 return 0;
823         }
824
825         if (flags & MPOL_F_ADDR) {
826                 /*
827                  * Do NOT fall back to task policy if the
828                  * vma/shared policy at addr is NULL.  We
829                  * want to return MPOL_DEFAULT in this case.
830                  */
831                 down_read(&mm->mmap_sem);
832                 vma = find_vma_intersection(mm, addr, addr+1);
833                 if (!vma) {
834                         up_read(&mm->mmap_sem);
835                         return -EFAULT;
836                 }
837                 if (vma->vm_ops && vma->vm_ops->get_policy)
838                         pol = vma->vm_ops->get_policy(vma, addr);
839                 else
840                         pol = vma->vm_policy;
841         } else if (addr)
842                 return -EINVAL;
843
844         if (!pol)
845                 pol = &default_policy;  /* indicates default behavior */
846
847         if (flags & MPOL_F_NODE) {
848                 if (flags & MPOL_F_ADDR) {
849                         err = lookup_node(mm, addr);
850                         if (err < 0)
851                                 goto out;
852                         *policy = err;
853                 } else if (pol == current->mempolicy &&
854                                 pol->mode == MPOL_INTERLEAVE) {
855                         *policy = current->il_next;
856                 } else {
857                         err = -EINVAL;
858                         goto out;
859                 }
860         } else {
861                 *policy = pol == &default_policy ? MPOL_DEFAULT :
862                                                 pol->mode;
863                 /*
864                  * Internal mempolicy flags must be masked off before exposing
865                  * the policy to userspace.
866                  */
867                 *policy |= (pol->flags & MPOL_MODE_FLAGS);
868         }
869
870         if (vma) {
871                 up_read(&current->mm->mmap_sem);
872                 vma = NULL;
873         }
874
875         err = 0;
876         if (nmask) {
877                 if (mpol_store_user_nodemask(pol)) {
878                         *nmask = pol->w.user_nodemask;
879                 } else {
880                         task_lock(current);
881                         get_policy_nodemask(pol, nmask);
882                         task_unlock(current);
883                 }
884         }
885
886  out:
887         mpol_cond_put(pol);
888         if (vma)
889                 up_read(&current->mm->mmap_sem);
890         return err;
891 }
892
893 #ifdef CONFIG_MIGRATION
894 /*
895  * page migration
896  */
897 static void migrate_page_add(struct page *page, struct list_head *pagelist,
898                                 unsigned long flags)
899 {
900         /*
901          * Avoid migrating a page that is shared with others.
902          */
903         if ((flags & MPOL_MF_MOVE_ALL) || page_mapcount(page) == 1) {
904                 if (!isolate_lru_page(page)) {
905                         list_add_tail(&page->lru, pagelist);
906                         inc_zone_page_state(page, NR_ISOLATED_ANON +
907                                             page_is_file_cache(page));
908                 }
909         }
910 }
911
912 static struct page *new_node_page(struct page *page, unsigned long node, int **x)
913 {
914         return alloc_pages_exact_node(node, GFP_HIGHUSER_MOVABLE, 0);
915 }
916
917 /*
918  * Migrate pages from one node to a target node.
919  * Returns error or the number of pages not migrated.
920  */
921 static int migrate_to_node(struct mm_struct *mm, int source, int dest,
922                            int flags)
923 {
924         nodemask_t nmask;
925         LIST_HEAD(pagelist);
926         int err = 0;
927
928         nodes_clear(nmask);
929         node_set(source, nmask);
930
931         check_range(mm, mm->mmap->vm_start, mm->task_size, &nmask,
932                         flags | MPOL_MF_DISCONTIG_OK, &pagelist);
933
934         if (!list_empty(&pagelist)) {
935                 err = migrate_pages(&pagelist, new_node_page, dest, 0);
936                 if (err)
937                         putback_lru_pages(&pagelist);
938         }
939
940         return err;
941 }
942
943 /*
944  * Move pages between the two nodesets so as to preserve the physical
945  * layout as much as possible.
946  *
947  * Returns the number of page that could not be moved.
948  */
949 int do_migrate_pages(struct mm_struct *mm,
950         const nodemask_t *from_nodes, const nodemask_t *to_nodes, int flags)
951 {
952         int busy = 0;
953         int err;
954         nodemask_t tmp;
955
956         err = migrate_prep();
957         if (err)
958                 return err;
959
960         down_read(&mm->mmap_sem);
961
962         err = migrate_vmas(mm, from_nodes, to_nodes, flags);
963         if (err)
964                 goto out;
965
966         /*
967          * Find a 'source' bit set in 'tmp' whose corresponding 'dest'
968          * bit in 'to' is not also set in 'tmp'.  Clear the found 'source'
969          * bit in 'tmp', and return that <source, dest> pair for migration.
970          * The pair of nodemasks 'to' and 'from' define the map.
971          *
972          * If no pair of bits is found that way, fallback to picking some
973          * pair of 'source' and 'dest' bits that are not the same.  If the
974          * 'source' and 'dest' bits are the same, this represents a node
975          * that will be migrating to itself, so no pages need move.
976          *
977          * If no bits are left in 'tmp', or if all remaining bits left
978          * in 'tmp' correspond to the same bit in 'to', return false
979          * (nothing left to migrate).
980          *
981          * This lets us pick a pair of nodes to migrate between, such that
982          * if possible the dest node is not already occupied by some other
983          * source node, minimizing the risk of overloading the memory on a
984          * node that would happen if we migrated incoming memory to a node
985          * before migrating outgoing memory source that same node.
986          *
987          * A single scan of tmp is sufficient.  As we go, we remember the
988          * most recent <s, d> pair that moved (s != d).  If we find a pair
989          * that not only moved, but what's better, moved to an empty slot
990          * (d is not set in tmp), then we break out then, with that pair.
991          * Otherwise when we finish scannng from_tmp, we at least have the
992          * most recent <s, d> pair that moved.  If we get all the way through
993          * the scan of tmp without finding any node that moved, much less
994          * moved to an empty node, then there is nothing left worth migrating.
995          */
996
997         tmp = *from_nodes;
998         while (!nodes_empty(tmp)) {
999                 int s,d;
1000                 int source = -1;
1001                 int dest = 0;
1002
1003                 for_each_node_mask(s, tmp) {
1004                         d = node_remap(s, *from_nodes, *to_nodes);
1005                         if (s == d)
1006                                 continue;
1007
1008                         source = s;     /* Node moved. Memorize */
1009                         dest = d;
1010
1011                         /* dest not in remaining from nodes? */
1012                         if (!node_isset(dest, tmp))
1013                                 break;
1014                 }
1015                 if (source == -1)
1016                         break;
1017
1018                 node_clear(source, tmp);
1019                 err = migrate_to_node(mm, source, dest, flags);
1020                 if (err > 0)
1021                         busy += err;
1022                 if (err < 0)
1023                         break;
1024         }
1025 out:
1026         up_read(&mm->mmap_sem);
1027         if (err < 0)
1028                 return err;
1029         return busy;
1030
1031 }
1032
1033 /*
1034  * Allocate a new page for page migration based on vma policy.
1035  * Start assuming that page is mapped by vma pointed to by @private.
1036  * Search forward from there, if not.  N.B., this assumes that the
1037  * list of pages handed to migrate_pages()--which is how we get here--
1038  * is in virtual address order.
1039  */
1040 static struct page *new_vma_page(struct page *page, unsigned long private, int **x)
1041 {
1042         struct vm_area_struct *vma = (struct vm_area_struct *)private;
1043         unsigned long uninitialized_var(address);
1044
1045         while (vma) {
1046                 address = page_address_in_vma(page, vma);
1047                 if (address != -EFAULT)
1048                         break;
1049                 vma = vma->vm_next;
1050         }
1051
1052         /*
1053          * if !vma, alloc_page_vma() will use task or system default policy
1054          */
1055         return alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, address);
1056 }
1057 #else
1058
1059 static void migrate_page_add(struct page *page, struct list_head *pagelist,
1060                                 unsigned long flags)
1061 {
1062 }
1063
1064 int do_migrate_pages(struct mm_struct *mm,
1065         const nodemask_t *from_nodes, const nodemask_t *to_nodes, int flags)
1066 {
1067         return -ENOSYS;
1068 }
1069
1070 static struct page *new_vma_page(struct page *page, unsigned long private, int **x)
1071 {
1072         return NULL;
1073 }
1074 #endif
1075
1076 static long do_mbind(unsigned long start, unsigned long len,
1077                      unsigned short mode, unsigned short mode_flags,
1078                      nodemask_t *nmask, unsigned long flags)
1079 {
1080         struct vm_area_struct *vma;
1081         struct mm_struct *mm = current->mm;
1082         struct mempolicy *new;
1083         unsigned long end;
1084         int err;
1085         LIST_HEAD(pagelist);
1086
1087         if (flags & ~(unsigned long)(MPOL_MF_STRICT |
1088                                      MPOL_MF_MOVE | MPOL_MF_MOVE_ALL))
1089                 return -EINVAL;
1090         if ((flags & MPOL_MF_MOVE_ALL) && !capable(CAP_SYS_NICE))
1091                 return -EPERM;
1092
1093         if (start & ~PAGE_MASK)
1094                 return -EINVAL;
1095
1096         if (mode == MPOL_DEFAULT)
1097                 flags &= ~MPOL_MF_STRICT;
1098
1099         len = (len + PAGE_SIZE - 1) & PAGE_MASK;
1100         end = start + len;
1101
1102         if (end < start)
1103                 return -EINVAL;
1104         if (end == start)
1105                 return 0;
1106
1107         new = mpol_new(mode, mode_flags, nmask);
1108         if (IS_ERR(new))
1109                 return PTR_ERR(new);
1110
1111         /*
1112          * If we are using the default policy then operation
1113          * on discontinuous address spaces is okay after all
1114          */
1115         if (!new)
1116                 flags |= MPOL_MF_DISCONTIG_OK;
1117
1118         pr_debug("mbind %lx-%lx mode:%d flags:%d nodes:%lx\n",
1119                  start, start + len, mode, mode_flags,
1120                  nmask ? nodes_addr(*nmask)[0] : -1);
1121
1122         if (flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)) {
1123
1124                 err = migrate_prep();
1125                 if (err)
1126                         goto mpol_out;
1127         }
1128         {
1129                 NODEMASK_SCRATCH(scratch);
1130                 if (scratch) {
1131                         down_write(&mm->mmap_sem);
1132                         task_lock(current);
1133                         err = mpol_set_nodemask(new, nmask, scratch);
1134                         task_unlock(current);
1135                         if (err)
1136                                 up_write(&mm->mmap_sem);
1137                 } else
1138                         err = -ENOMEM;
1139                 NODEMASK_SCRATCH_FREE(scratch);
1140         }
1141         if (err)
1142                 goto mpol_out;
1143
1144         vma = check_range(mm, start, end, nmask,
1145                           flags | MPOL_MF_INVERT, &pagelist);
1146
1147         err = PTR_ERR(vma);
1148         if (!IS_ERR(vma)) {
1149                 int nr_failed = 0;
1150
1151                 err = mbind_range(mm, start, end, new);
1152
1153                 if (!list_empty(&pagelist)) {
1154                         nr_failed = migrate_pages(&pagelist, new_vma_page,
1155                                                 (unsigned long)vma, 0);
1156                         if (nr_failed)
1157                                 putback_lru_pages(&pagelist);
1158                 }
1159
1160                 if (!err && nr_failed && (flags & MPOL_MF_STRICT))
1161                         err = -EIO;
1162         } else
1163                 putback_lru_pages(&pagelist);
1164
1165         up_write(&mm->mmap_sem);
1166  mpol_out:
1167         mpol_put(new);
1168         return err;
1169 }
1170
1171 /*
1172  * User space interface with variable sized bitmaps for nodelists.
1173  */
1174
1175 /* Copy a node mask from user space. */
1176 static int get_nodes(nodemask_t *nodes, const unsigned long __user *nmask,
1177                      unsigned long maxnode)
1178 {
1179         unsigned long k;
1180         unsigned long nlongs;
1181         unsigned long endmask;
1182
1183         --maxnode;
1184         nodes_clear(*nodes);
1185         if (maxnode == 0 || !nmask)
1186                 return 0;
1187         if (maxnode > PAGE_SIZE*BITS_PER_BYTE)
1188                 return -EINVAL;
1189
1190         nlongs = BITS_TO_LONGS(maxnode);
1191         if ((maxnode % BITS_PER_LONG) == 0)
1192                 endmask = ~0UL;
1193         else
1194                 endmask = (1UL << (maxnode % BITS_PER_LONG)) - 1;
1195
1196         /* When the user specified more nodes than supported just check
1197            if the non supported part is all zero. */
1198         if (nlongs > BITS_TO_LONGS(MAX_NUMNODES)) {
1199                 if (nlongs > PAGE_SIZE/sizeof(long))
1200                         return -EINVAL;
1201                 for (k = BITS_TO_LONGS(MAX_NUMNODES); k < nlongs; k++) {
1202                         unsigned long t;
1203                         if (get_user(t, nmask + k))
1204                                 return -EFAULT;
1205                         if (k == nlongs - 1) {
1206                                 if (t & endmask)
1207                                         return -EINVAL;
1208                         } else if (t)
1209                                 return -EINVAL;
1210                 }
1211                 nlongs = BITS_TO_LONGS(MAX_NUMNODES);
1212                 endmask = ~0UL;
1213         }
1214
1215         if (copy_from_user(nodes_addr(*nodes), nmask, nlongs*sizeof(unsigned long)))
1216                 return -EFAULT;
1217         nodes_addr(*nodes)[nlongs-1] &= endmask;
1218         return 0;
1219 }
1220
1221 /* Copy a kernel node mask to user space */
1222 static int copy_nodes_to_user(unsigned long __user *mask, unsigned long maxnode,
1223                               nodemask_t *nodes)
1224 {
1225         unsigned long copy = ALIGN(maxnode-1, 64) / 8;
1226         const int nbytes = BITS_TO_LONGS(MAX_NUMNODES) * sizeof(long);
1227
1228         if (copy > nbytes) {
1229                 if (copy > PAGE_SIZE)
1230                         return -EINVAL;
1231                 if (clear_user((char __user *)mask + nbytes, copy - nbytes))
1232                         return -EFAULT;
1233                 copy = nbytes;
1234         }
1235         return copy_to_user(mask, nodes_addr(*nodes), copy) ? -EFAULT : 0;
1236 }
1237
1238 SYSCALL_DEFINE6(mbind, unsigned long, start, unsigned long, len,
1239                 unsigned long, mode, unsigned long __user *, nmask,
1240                 unsigned long, maxnode, unsigned, flags)
1241 {
1242         nodemask_t nodes;
1243         int err;
1244         unsigned short mode_flags;
1245
1246         mode_flags = mode & MPOL_MODE_FLAGS;
1247         mode &= ~MPOL_MODE_FLAGS;
1248         if (mode >= MPOL_MAX)
1249                 return -EINVAL;
1250         if ((mode_flags & MPOL_F_STATIC_NODES) &&
1251             (mode_flags & MPOL_F_RELATIVE_NODES))
1252                 return -EINVAL;
1253         err = get_nodes(&nodes, nmask, maxnode);
1254         if (err)
1255                 return err;
1256         return do_mbind(start, len, mode, mode_flags, &nodes, flags);
1257 }
1258
1259 /* Set the process memory policy */
1260 SYSCALL_DEFINE3(set_mempolicy, int, mode, unsigned long __user *, nmask,
1261                 unsigned long, maxnode)
1262 {
1263         int err;
1264         nodemask_t nodes;
1265         unsigned short flags;
1266
1267         flags = mode & MPOL_MODE_FLAGS;
1268         mode &= ~MPOL_MODE_FLAGS;
1269         if ((unsigned int)mode >= MPOL_MAX)
1270                 return -EINVAL;
1271         if ((flags & MPOL_F_STATIC_NODES) && (flags & MPOL_F_RELATIVE_NODES))
1272                 return -EINVAL;
1273         err = get_nodes(&nodes, nmask, maxnode);
1274         if (err)
1275                 return err;
1276         return do_set_mempolicy(mode, flags, &nodes);
1277 }
1278
1279 SYSCALL_DEFINE4(migrate_pages, pid_t, pid, unsigned long, maxnode,
1280                 const unsigned long __user *, old_nodes,
1281                 const unsigned long __user *, new_nodes)
1282 {
1283         const struct cred *cred = current_cred(), *tcred;
1284         struct mm_struct *mm = NULL;
1285         struct task_struct *task;
1286         nodemask_t task_nodes;
1287         int err;
1288         nodemask_t *old;
1289         nodemask_t *new;
1290         NODEMASK_SCRATCH(scratch);
1291
1292         if (!scratch)
1293                 return -ENOMEM;
1294
1295         old = &scratch->mask1;
1296         new = &scratch->mask2;
1297
1298         err = get_nodes(old, old_nodes, maxnode);
1299         if (err)
1300                 goto out;
1301
1302         err = get_nodes(new, new_nodes, maxnode);
1303         if (err)
1304                 goto out;
1305
1306         /* Find the mm_struct */
1307         read_lock(&tasklist_lock);
1308         task = pid ? find_task_by_vpid(pid) : current;
1309         if (!task) {
1310                 read_unlock(&tasklist_lock);
1311                 err = -ESRCH;
1312                 goto out;
1313         }
1314         mm = get_task_mm(task);
1315         read_unlock(&tasklist_lock);
1316
1317         err = -EINVAL;
1318         if (!mm)
1319                 goto out;
1320
1321         /*
1322          * Check if this process has the right to modify the specified
1323          * process. The right exists if the process has administrative
1324          * capabilities, superuser privileges or the same
1325          * userid as the target process.
1326          */
1327         rcu_read_lock();
1328         tcred = __task_cred(task);
1329         if (cred->euid != tcred->suid && cred->euid != tcred->uid &&
1330             cred->uid  != tcred->suid && cred->uid  != tcred->uid &&
1331             !capable(CAP_SYS_NICE)) {
1332                 rcu_read_unlock();
1333                 err = -EPERM;
1334                 goto out;
1335         }
1336         rcu_read_unlock();
1337
1338         task_nodes = cpuset_mems_allowed(task);
1339         /* Is the user allowed to access the target nodes? */
1340         if (!nodes_subset(*new, task_nodes) && !capable(CAP_SYS_NICE)) {
1341                 err = -EPERM;
1342                 goto out;
1343         }
1344
1345         if (!nodes_subset(*new, node_states[N_HIGH_MEMORY])) {
1346                 err = -EINVAL;
1347                 goto out;
1348         }
1349
1350         err = security_task_movememory(task);
1351         if (err)
1352                 goto out;
1353
1354         err = do_migrate_pages(mm, old, new,
1355                 capable(CAP_SYS_NICE) ? MPOL_MF_MOVE_ALL : MPOL_MF_MOVE);
1356 out:
1357         if (mm)
1358                 mmput(mm);
1359         NODEMASK_SCRATCH_FREE(scratch);
1360
1361         return err;
1362 }
1363
1364
1365 /* Retrieve NUMA policy */
1366 SYSCALL_DEFINE5(get_mempolicy, int __user *, policy,
1367                 unsigned long __user *, nmask, unsigned long, maxnode,
1368                 unsigned long, addr, unsigned long, flags)
1369 {
1370         int err;
1371         int uninitialized_var(pval);
1372         nodemask_t nodes;
1373
1374         if (nmask != NULL && maxnode < MAX_NUMNODES)
1375                 return -EINVAL;
1376
1377         err = do_get_mempolicy(&pval, &nodes, addr, flags);
1378
1379         if (err)
1380                 return err;
1381
1382         if (policy && put_user(pval, policy))
1383                 return -EFAULT;
1384
1385         if (nmask)
1386                 err = copy_nodes_to_user(nmask, maxnode, &nodes);
1387
1388         return err;
1389 }
1390
1391 #ifdef CONFIG_COMPAT
1392
1393 asmlinkage long compat_sys_get_mempolicy(int __user *policy,
1394                                      compat_ulong_t __user *nmask,
1395                                      compat_ulong_t maxnode,
1396                                      compat_ulong_t addr, compat_ulong_t flags)
1397 {
1398         long err;
1399         unsigned long __user *nm = NULL;
1400         unsigned long nr_bits, alloc_size;
1401         DECLARE_BITMAP(bm, MAX_NUMNODES);
1402
1403         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1404         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1405
1406         if (nmask)
1407                 nm = compat_alloc_user_space(alloc_size);
1408
1409         err = sys_get_mempolicy(policy, nm, nr_bits+1, addr, flags);
1410
1411         if (!err && nmask) {
1412                 err = copy_from_user(bm, nm, alloc_size);
1413                 /* ensure entire bitmap is zeroed */
1414                 err |= clear_user(nmask, ALIGN(maxnode-1, 8) / 8);
1415                 err |= compat_put_bitmap(nmask, bm, nr_bits);
1416         }
1417
1418         return err;
1419 }
1420
1421 asmlinkage long compat_sys_set_mempolicy(int mode, compat_ulong_t __user *nmask,
1422                                      compat_ulong_t maxnode)
1423 {
1424         long err = 0;
1425         unsigned long __user *nm = NULL;
1426         unsigned long nr_bits, alloc_size;
1427         DECLARE_BITMAP(bm, MAX_NUMNODES);
1428
1429         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1430         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1431
1432         if (nmask) {
1433                 err = compat_get_bitmap(bm, nmask, nr_bits);
1434                 nm = compat_alloc_user_space(alloc_size);
1435                 err |= copy_to_user(nm, bm, alloc_size);
1436         }
1437
1438         if (err)
1439                 return -EFAULT;
1440
1441         return sys_set_mempolicy(mode, nm, nr_bits+1);
1442 }
1443
1444 asmlinkage long compat_sys_mbind(compat_ulong_t start, compat_ulong_t len,
1445                              compat_ulong_t mode, compat_ulong_t __user *nmask,
1446                              compat_ulong_t maxnode, compat_ulong_t flags)
1447 {
1448         long err = 0;
1449         unsigned long __user *nm = NULL;
1450         unsigned long nr_bits, alloc_size;
1451         nodemask_t bm;
1452
1453         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1454         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1455
1456         if (nmask) {
1457                 err = compat_get_bitmap(nodes_addr(bm), nmask, nr_bits);
1458                 nm = compat_alloc_user_space(alloc_size);
1459                 err |= copy_to_user(nm, nodes_addr(bm), alloc_size);
1460         }
1461
1462         if (err)
1463                 return -EFAULT;
1464
1465         return sys_mbind(start, len, mode, nm, nr_bits+1, flags);
1466 }
1467
1468 #endif
1469
1470 /*
1471  * get_vma_policy(@task, @vma, @addr)
1472  * @task - task for fallback if vma policy == default
1473  * @vma   - virtual memory area whose policy is sought
1474  * @addr  - address in @vma for shared policy lookup
1475  *
1476  * Returns effective policy for a VMA at specified address.
1477  * Falls back to @task or system default policy, as necessary.
1478  * Current or other task's task mempolicy and non-shared vma policies
1479  * are protected by the task's mmap_sem, which must be held for read by
1480  * the caller.
1481  * Shared policies [those marked as MPOL_F_SHARED] require an extra reference
1482  * count--added by the get_policy() vm_op, as appropriate--to protect against
1483  * freeing by another task.  It is the caller's responsibility to free the
1484  * extra reference for shared policies.
1485  */
1486 static struct mempolicy *get_vma_policy(struct task_struct *task,
1487                 struct vm_area_struct *vma, unsigned long addr)
1488 {
1489         struct mempolicy *pol = task->mempolicy;
1490
1491         if (vma) {
1492                 if (vma->vm_ops && vma->vm_ops->get_policy) {
1493                         struct mempolicy *vpol = vma->vm_ops->get_policy(vma,
1494                                                                         addr);
1495                         if (vpol)
1496                                 pol = vpol;
1497                 } else if (vma->vm_policy)
1498                         pol = vma->vm_policy;
1499         }
1500         if (!pol)
1501                 pol = &default_policy;
1502         return pol;
1503 }
1504
1505 /*
1506  * Return a nodemask representing a mempolicy for filtering nodes for
1507  * page allocation
1508  */
1509 static nodemask_t *policy_nodemask(gfp_t gfp, struct mempolicy *policy)
1510 {
1511         /* Lower zones don't get a nodemask applied for MPOL_BIND */
1512         if (unlikely(policy->mode == MPOL_BIND) &&
1513                         gfp_zone(gfp) >= policy_zone &&
1514                         cpuset_nodemask_valid_mems_allowed(&policy->v.nodes))
1515                 return &policy->v.nodes;
1516
1517         return NULL;
1518 }
1519
1520 /* Return a zonelist indicated by gfp for node representing a mempolicy */
1521 static struct zonelist *policy_zonelist(gfp_t gfp, struct mempolicy *policy)
1522 {
1523         int nd = numa_node_id();
1524
1525         switch (policy->mode) {
1526         case MPOL_PREFERRED:
1527                 if (!(policy->flags & MPOL_F_LOCAL))
1528                         nd = policy->v.preferred_node;
1529                 break;
1530         case MPOL_BIND:
1531                 /*
1532                  * Normally, MPOL_BIND allocations are node-local within the
1533                  * allowed nodemask.  However, if __GFP_THISNODE is set and the
1534                  * current node isn't part of the mask, we use the zonelist for
1535                  * the first node in the mask instead.
1536                  */
1537                 if (unlikely(gfp & __GFP_THISNODE) &&
1538                                 unlikely(!node_isset(nd, policy->v.nodes)))
1539                         nd = first_node(policy->v.nodes);
1540                 break;
1541         default:
1542                 BUG();
1543         }
1544         return node_zonelist(nd, gfp);
1545 }
1546
1547 /* Do dynamic interleaving for a process */
1548 static unsigned interleave_nodes(struct mempolicy *policy)
1549 {
1550         unsigned nid, next;
1551         struct task_struct *me = current;
1552
1553         nid = me->il_next;
1554         next = next_node(nid, policy->v.nodes);
1555         if (next >= MAX_NUMNODES)
1556                 next = first_node(policy->v.nodes);
1557         if (next < MAX_NUMNODES)
1558                 me->il_next = next;
1559         return nid;
1560 }
1561
1562 /*
1563  * Depending on the memory policy provide a node from which to allocate the
1564  * next slab entry.
1565  * @policy must be protected by freeing by the caller.  If @policy is
1566  * the current task's mempolicy, this protection is implicit, as only the
1567  * task can change it's policy.  The system default policy requires no
1568  * such protection.
1569  */
1570 unsigned slab_node(struct mempolicy *policy)
1571 {
1572         if (!policy || policy->flags & MPOL_F_LOCAL)
1573                 return numa_node_id();
1574
1575         switch (policy->mode) {
1576         case MPOL_PREFERRED:
1577                 /*
1578                  * handled MPOL_F_LOCAL above
1579                  */
1580                 return policy->v.preferred_node;
1581
1582         case MPOL_INTERLEAVE:
1583                 return interleave_nodes(policy);
1584
1585         case MPOL_BIND: {
1586                 /*
1587                  * Follow bind policy behavior and start allocation at the
1588                  * first node.
1589                  */
1590                 struct zonelist *zonelist;
1591                 struct zone *zone;
1592                 enum zone_type highest_zoneidx = gfp_zone(GFP_KERNEL);
1593                 zonelist = &NODE_DATA(numa_node_id())->node_zonelists[0];
1594                 (void)first_zones_zonelist(zonelist, highest_zoneidx,
1595                                                         &policy->v.nodes,
1596                                                         &zone);
1597                 return zone->node;
1598         }
1599
1600         default:
1601                 BUG();
1602         }
1603 }
1604
1605 /* Do static interleaving for a VMA with known offset. */
1606 static unsigned offset_il_node(struct mempolicy *pol,
1607                 struct vm_area_struct *vma, unsigned long off)
1608 {
1609         unsigned nnodes = nodes_weight(pol->v.nodes);
1610         unsigned target;
1611         int c;
1612         int nid = -1;
1613
1614         if (!nnodes)
1615                 return numa_node_id();
1616         target = (unsigned int)off % nnodes;
1617         c = 0;
1618         do {
1619                 nid = next_node(nid, pol->v.nodes);
1620                 c++;
1621         } while (c <= target);
1622         return nid;
1623 }
1624
1625 /* Determine a node number for interleave */
1626 static inline unsigned interleave_nid(struct mempolicy *pol,
1627                  struct vm_area_struct *vma, unsigned long addr, int shift)
1628 {
1629         if (vma) {
1630                 unsigned long off;
1631
1632                 /*
1633                  * for small pages, there is no difference between
1634                  * shift and PAGE_SHIFT, so the bit-shift is safe.
1635                  * for huge pages, since vm_pgoff is in units of small
1636                  * pages, we need to shift off the always 0 bits to get
1637                  * a useful offset.
1638                  */
1639                 BUG_ON(shift < PAGE_SHIFT);
1640                 off = vma->vm_pgoff >> (shift - PAGE_SHIFT);
1641                 off += (addr - vma->vm_start) >> shift;
1642                 return offset_il_node(pol, vma, off);
1643         } else
1644                 return interleave_nodes(pol);
1645 }
1646
1647 #ifdef CONFIG_HUGETLBFS
1648 /*
1649  * huge_zonelist(@vma, @addr, @gfp_flags, @mpol)
1650  * @vma = virtual memory area whose policy is sought
1651  * @addr = address in @vma for shared policy lookup and interleave policy
1652  * @gfp_flags = for requested zone
1653  * @mpol = pointer to mempolicy pointer for reference counted mempolicy
1654  * @nodemask = pointer to nodemask pointer for MPOL_BIND nodemask
1655  *
1656  * Returns a zonelist suitable for a huge page allocation and a pointer
1657  * to the struct mempolicy for conditional unref after allocation.
1658  * If the effective policy is 'BIND, returns a pointer to the mempolicy's
1659  * @nodemask for filtering the zonelist.
1660  *
1661  * Must be protected by get_mems_allowed()
1662  */
1663 struct zonelist *huge_zonelist(struct vm_area_struct *vma, unsigned long addr,
1664                                 gfp_t gfp_flags, struct mempolicy **mpol,
1665                                 nodemask_t **nodemask)
1666 {
1667         struct zonelist *zl;
1668
1669         *mpol = get_vma_policy(current, vma, addr);
1670         *nodemask = NULL;       /* assume !MPOL_BIND */
1671
1672         if (unlikely((*mpol)->mode == MPOL_INTERLEAVE)) {
1673                 zl = node_zonelist(interleave_nid(*mpol, vma, addr,
1674                                 huge_page_shift(hstate_vma(vma))), gfp_flags);
1675         } else {
1676                 zl = policy_zonelist(gfp_flags, *mpol);
1677                 if ((*mpol)->mode == MPOL_BIND)
1678                         *nodemask = &(*mpol)->v.nodes;
1679         }
1680         return zl;
1681 }
1682
1683 /*
1684  * init_nodemask_of_mempolicy
1685  *
1686  * If the current task's mempolicy is "default" [NULL], return 'false'
1687  * to indicate default policy.  Otherwise, extract the policy nodemask
1688  * for 'bind' or 'interleave' policy into the argument nodemask, or
1689  * initialize the argument nodemask to contain the single node for
1690  * 'preferred' or 'local' policy and return 'true' to indicate presence
1691  * of non-default mempolicy.
1692  *
1693  * We don't bother with reference counting the mempolicy [mpol_get/put]
1694  * because the current task is examining it's own mempolicy and a task's
1695  * mempolicy is only ever changed by the task itself.
1696  *
1697  * N.B., it is the caller's responsibility to free a returned nodemask.
1698  */
1699 bool init_nodemask_of_mempolicy(nodemask_t *mask)
1700 {
1701         struct mempolicy *mempolicy;
1702         int nid;
1703
1704         if (!(mask && current->mempolicy))
1705                 return false;
1706
1707         task_lock(current);
1708         mempolicy = current->mempolicy;
1709         switch (mempolicy->mode) {
1710         case MPOL_PREFERRED:
1711                 if (mempolicy->flags & MPOL_F_LOCAL)
1712                         nid = numa_node_id();
1713                 else
1714                         nid = mempolicy->v.preferred_node;
1715                 init_nodemask_of_node(mask, nid);
1716                 break;
1717
1718         case MPOL_BIND:
1719                 /* Fall through */
1720         case MPOL_INTERLEAVE:
1721                 *mask =  mempolicy->v.nodes;
1722                 break;
1723
1724         default:
1725                 BUG();
1726         }
1727         task_unlock(current);
1728
1729         return true;
1730 }
1731 #endif
1732
1733 /*
1734  * mempolicy_nodemask_intersects
1735  *
1736  * If tsk's mempolicy is "default" [NULL], return 'true' to indicate default
1737  * policy.  Otherwise, check for intersection between mask and the policy
1738  * nodemask for 'bind' or 'interleave' policy.  For 'perferred' or 'local'
1739  * policy, always return true since it may allocate elsewhere on fallback.
1740  *
1741  * Takes task_lock(tsk) to prevent freeing of its mempolicy.
1742  */
1743 bool mempolicy_nodemask_intersects(struct task_struct *tsk,
1744                                         const nodemask_t *mask)
1745 {
1746         struct mempolicy *mempolicy;
1747         bool ret = true;
1748
1749         if (!mask)
1750                 return ret;
1751         task_lock(tsk);
1752         mempolicy = tsk->mempolicy;
1753         if (!mempolicy)
1754                 goto out;
1755
1756         switch (mempolicy->mode) {
1757         case MPOL_PREFERRED:
1758                 /*
1759                  * MPOL_PREFERRED and MPOL_F_LOCAL are only preferred nodes to
1760                  * allocate from, they may fallback to other nodes when oom.
1761                  * Thus, it's possible for tsk to have allocated memory from
1762                  * nodes in mask.
1763                  */
1764                 break;
1765         case MPOL_BIND:
1766         case MPOL_INTERLEAVE:
1767                 ret = nodes_intersects(mempolicy->v.nodes, *mask);
1768                 break;
1769         default:
1770                 BUG();
1771         }
1772 out:
1773         task_unlock(tsk);
1774         return ret;
1775 }
1776
1777 /* Allocate a page in interleaved policy.
1778    Own path because it needs to do special accounting. */
1779 static struct page *alloc_page_interleave(gfp_t gfp, unsigned order,
1780                                         unsigned nid)
1781 {
1782         struct zonelist *zl;
1783         struct page *page;
1784
1785         zl = node_zonelist(nid, gfp);
1786         page = __alloc_pages(gfp, order, zl);
1787         if (page && page_zone(page) == zonelist_zone(&zl->_zonerefs[0]))
1788                 inc_zone_page_state(page, NUMA_INTERLEAVE_HIT);
1789         return page;
1790 }
1791
1792 /**
1793  *      alloc_page_vma  - Allocate a page for a VMA.
1794  *
1795  *      @gfp:
1796  *      %GFP_USER    user allocation.
1797  *      %GFP_KERNEL  kernel allocations,
1798  *      %GFP_HIGHMEM highmem/user allocations,
1799  *      %GFP_FS      allocation should not call back into a file system.
1800  *      %GFP_ATOMIC  don't sleep.
1801  *
1802  *      @vma:  Pointer to VMA or NULL if not available.
1803  *      @addr: Virtual Address of the allocation. Must be inside the VMA.
1804  *
1805  *      This function allocates a page from the kernel page pool and applies
1806  *      a NUMA policy associated with the VMA or the current process.
1807  *      When VMA is not NULL caller must hold down_read on the mmap_sem of the
1808  *      mm_struct of the VMA to prevent it from going away. Should be used for
1809  *      all allocations for pages that will be mapped into
1810  *      user space. Returns NULL when no page can be allocated.
1811  *
1812  *      Should be called with the mm_sem of the vma hold.
1813  */
1814 struct page *
1815 alloc_page_vma(gfp_t gfp, struct vm_area_struct *vma, unsigned long addr)
1816 {
1817         struct mempolicy *pol = get_vma_policy(current, vma, addr);
1818         struct zonelist *zl;
1819         struct page *page;
1820
1821         get_mems_allowed();
1822         if (unlikely(pol->mode == MPOL_INTERLEAVE)) {
1823                 unsigned nid;
1824
1825                 nid = interleave_nid(pol, vma, addr, PAGE_SHIFT);
1826                 mpol_cond_put(pol);
1827                 page = alloc_page_interleave(gfp, 0, nid);
1828                 put_mems_allowed();
1829                 return page;
1830         }
1831         zl = policy_zonelist(gfp, pol);
1832         if (unlikely(mpol_needs_cond_ref(pol))) {
1833                 /*
1834                  * slow path: ref counted shared policy
1835                  */
1836                 struct page *page =  __alloc_pages_nodemask(gfp, 0,
1837                                                 zl, policy_nodemask(gfp, pol));
1838                 __mpol_put(pol);
1839                 put_mems_allowed();
1840                 return page;
1841         }
1842         /*
1843          * fast path:  default or task policy
1844          */
1845         page = __alloc_pages_nodemask(gfp, 0, zl, policy_nodemask(gfp, pol));
1846         put_mems_allowed();
1847         return page;
1848 }
1849
1850 /**
1851  *      alloc_pages_current - Allocate pages.
1852  *
1853  *      @gfp:
1854  *              %GFP_USER   user allocation,
1855  *              %GFP_KERNEL kernel allocation,
1856  *              %GFP_HIGHMEM highmem allocation,
1857  *              %GFP_FS     don't call back into a file system.
1858  *              %GFP_ATOMIC don't sleep.
1859  *      @order: Power of two of allocation size in pages. 0 is a single page.
1860  *
1861  *      Allocate a page from the kernel page pool.  When not in
1862  *      interrupt context and apply the current process NUMA policy.
1863  *      Returns NULL when no page can be allocated.
1864  *
1865  *      Don't call cpuset_update_task_memory_state() unless
1866  *      1) it's ok to take cpuset_sem (can WAIT), and
1867  *      2) allocating for current task (not interrupt).
1868  */
1869 struct page *alloc_pages_current(gfp_t gfp, unsigned order)
1870 {
1871         struct mempolicy *pol = current->mempolicy;
1872         struct page *page;
1873
1874         if (!pol || in_interrupt() || (gfp & __GFP_THISNODE))
1875                 pol = &default_policy;
1876
1877         get_mems_allowed();
1878         /*
1879          * No reference counting needed for current->mempolicy
1880          * nor system default_policy
1881          */
1882         if (pol->mode == MPOL_INTERLEAVE)
1883                 page = alloc_page_interleave(gfp, order, interleave_nodes(pol));
1884         else
1885                 page = __alloc_pages_nodemask(gfp, order,
1886                         policy_zonelist(gfp, pol), policy_nodemask(gfp, pol));
1887         put_mems_allowed();
1888         return page;
1889 }
1890 EXPORT_SYMBOL(alloc_pages_current);
1891
1892 /*
1893  * If mpol_dup() sees current->cpuset == cpuset_being_rebound, then it
1894  * rebinds the mempolicy its copying by calling mpol_rebind_policy()
1895  * with the mems_allowed returned by cpuset_mems_allowed().  This
1896  * keeps mempolicies cpuset relative after its cpuset moves.  See
1897  * further kernel/cpuset.c update_nodemask().
1898  *
1899  * current's mempolicy may be rebinded by the other task(the task that changes
1900  * cpuset's mems), so we needn't do rebind work for current task.
1901  */
1902
1903 /* Slow path of a mempolicy duplicate */
1904 struct mempolicy *__mpol_dup(struct mempolicy *old)
1905 {
1906         struct mempolicy *new = kmem_cache_alloc(policy_cache, GFP_KERNEL);
1907
1908         if (!new)
1909                 return ERR_PTR(-ENOMEM);
1910
1911         /* task's mempolicy is protected by alloc_lock */
1912         if (old == current->mempolicy) {
1913                 task_lock(current);
1914                 *new = *old;
1915                 task_unlock(current);
1916         } else
1917                 *new = *old;
1918
1919         rcu_read_lock();
1920         if (current_cpuset_is_being_rebound()) {
1921                 nodemask_t mems = cpuset_mems_allowed(current);
1922                 if (new->flags & MPOL_F_REBINDING)
1923                         mpol_rebind_policy(new, &mems, MPOL_REBIND_STEP2);
1924                 else
1925                         mpol_rebind_policy(new, &mems, MPOL_REBIND_ONCE);
1926         }
1927         rcu_read_unlock();
1928         atomic_set(&new->refcnt, 1);
1929         return new;
1930 }
1931
1932 /*
1933  * If *frompol needs [has] an extra ref, copy *frompol to *tompol ,
1934  * eliminate the * MPOL_F_* flags that require conditional ref and
1935  * [NOTE!!!] drop the extra ref.  Not safe to reference *frompol directly
1936  * after return.  Use the returned value.
1937  *
1938  * Allows use of a mempolicy for, e.g., multiple allocations with a single
1939  * policy lookup, even if the policy needs/has extra ref on lookup.
1940  * shmem_readahead needs this.
1941  */
1942 struct mempolicy *__mpol_cond_copy(struct mempolicy *tompol,
1943                                                 struct mempolicy *frompol)
1944 {
1945         if (!mpol_needs_cond_ref(frompol))
1946                 return frompol;
1947
1948         *tompol = *frompol;
1949         tompol->flags &= ~MPOL_F_SHARED;        /* copy doesn't need unref */
1950         __mpol_put(frompol);
1951         return tompol;
1952 }
1953
1954 /* Slow path of a mempolicy comparison */
1955 int __mpol_equal(struct mempolicy *a, struct mempolicy *b)
1956 {
1957         if (!a || !b)
1958                 return 0;
1959         if (a->mode != b->mode)
1960                 return 0;
1961         if (a->flags != b->flags)
1962                 return 0;
1963         if (mpol_store_user_nodemask(a))
1964                 if (!nodes_equal(a->w.user_nodemask, b->w.user_nodemask))
1965                         return 0;
1966
1967         switch (a->mode) {
1968         case MPOL_BIND:
1969                 /* Fall through */
1970         case MPOL_INTERLEAVE:
1971                 return nodes_equal(a->v.nodes, b->v.nodes);
1972         case MPOL_PREFERRED:
1973                 return a->v.preferred_node == b->v.preferred_node &&
1974                         a->flags == b->flags;
1975         default:
1976                 BUG();
1977                 return 0;
1978         }
1979 }
1980
1981 /*
1982  * Shared memory backing store policy support.
1983  *
1984  * Remember policies even when nobody has shared memory mapped.
1985  * The policies are kept in Red-Black tree linked from the inode.
1986  * They are protected by the sp->lock spinlock, which should be held
1987  * for any accesses to the tree.
1988  */
1989
1990 /* lookup first element intersecting start-end */
1991 /* Caller holds sp->lock */
1992 static struct sp_node *
1993 sp_lookup(struct shared_policy *sp, unsigned long start, unsigned long end)
1994 {
1995         struct rb_node *n = sp->root.rb_node;
1996
1997         while (n) {
1998                 struct sp_node *p = rb_entry(n, struct sp_node, nd);
1999
2000                 if (start >= p->end)
2001                         n = n->rb_right;
2002                 else if (end <= p->start)
2003                         n = n->rb_left;
2004                 else
2005                         break;
2006         }
2007         if (!n)
2008                 return NULL;
2009         for (;;) {
2010                 struct sp_node *w = NULL;
2011                 struct rb_node *prev = rb_prev(n);
2012                 if (!prev)
2013                         break;
2014                 w = rb_entry(prev, struct sp_node, nd);
2015                 if (w->end <= start)
2016                         break;
2017                 n = prev;
2018         }
2019         return rb_entry(n, struct sp_node, nd);
2020 }
2021
2022 /* Insert a new shared policy into the list. */
2023 /* Caller holds sp->lock */
2024 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
2025 {
2026         struct rb_node **p = &sp->root.rb_node;
2027         struct rb_node *parent = NULL;
2028         struct sp_node *nd;
2029
2030         while (*p) {
2031                 parent = *p;
2032                 nd = rb_entry(parent, struct sp_node, nd);
2033                 if (new->start < nd->start)
2034                         p = &(*p)->rb_left;
2035                 else if (new->end > nd->end)
2036                         p = &(*p)->rb_right;
2037                 else
2038                         BUG();
2039         }
2040         rb_link_node(&new->nd, parent, p);
2041         rb_insert_color(&new->nd, &sp->root);
2042         pr_debug("inserting %lx-%lx: %d\n", new->start, new->end,
2043                  new->policy ? new->policy->mode : 0);
2044 }
2045
2046 /* Find shared policy intersecting idx */
2047 struct mempolicy *
2048 mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
2049 {
2050         struct mempolicy *pol = NULL;
2051         struct sp_node *sn;
2052
2053         if (!sp->root.rb_node)
2054                 return NULL;
2055         spin_lock(&sp->lock);
2056         sn = sp_lookup(sp, idx, idx+1);
2057         if (sn) {
2058                 mpol_get(sn->policy);
2059                 pol = sn->policy;
2060         }
2061         spin_unlock(&sp->lock);
2062         return pol;
2063 }
2064
2065 static void sp_delete(struct shared_policy *sp, struct sp_node *n)
2066 {
2067         pr_debug("deleting %lx-l%lx\n", n->start, n->end);
2068         rb_erase(&n->nd, &sp->root);
2069         mpol_put(n->policy);
2070         kmem_cache_free(sn_cache, n);
2071 }
2072
2073 static struct sp_node *sp_alloc(unsigned long start, unsigned long end,
2074                                 struct mempolicy *pol)
2075 {
2076         struct sp_node *n = kmem_cache_alloc(sn_cache, GFP_KERNEL);
2077
2078         if (!n)
2079                 return NULL;
2080         n->start = start;
2081         n->end = end;
2082         mpol_get(pol);
2083         pol->flags |= MPOL_F_SHARED;    /* for unref */
2084         n->policy = pol;
2085         return n;
2086 }
2087
2088 /* Replace a policy range. */
2089 static int shared_policy_replace(struct shared_policy *sp, unsigned long start,
2090                                  unsigned long end, struct sp_node *new)
2091 {
2092         struct sp_node *n, *new2 = NULL;
2093
2094 restart:
2095         spin_lock(&sp->lock);
2096         n = sp_lookup(sp, start, end);
2097         /* Take care of old policies in the same range. */
2098         while (n && n->start < end) {
2099                 struct rb_node *next = rb_next(&n->nd);
2100                 if (n->start >= start) {
2101                         if (n->end <= end)
2102                                 sp_delete(sp, n);
2103                         else
2104                                 n->start = end;
2105                 } else {
2106                         /* Old policy spanning whole new range. */
2107                         if (n->end > end) {
2108                                 if (!new2) {
2109                                         spin_unlock(&sp->lock);
2110                                         new2 = sp_alloc(end, n->end, n->policy);
2111                                         if (!new2)
2112                                                 return -ENOMEM;
2113                                         goto restart;
2114                                 }
2115                                 n->end = start;
2116                                 sp_insert(sp, new2);
2117                                 new2 = NULL;
2118                                 break;
2119                         } else
2120                                 n->end = start;
2121                 }
2122                 if (!next)
2123                         break;
2124                 n = rb_entry(next, struct sp_node, nd);
2125         }
2126         if (new)
2127                 sp_insert(sp, new);
2128         spin_unlock(&sp->lock);
2129         if (new2) {
2130                 mpol_put(new2->policy);
2131                 kmem_cache_free(sn_cache, new2);
2132         }
2133         return 0;
2134 }
2135
2136 /**
2137  * mpol_shared_policy_init - initialize shared policy for inode
2138  * @sp: pointer to inode shared policy
2139  * @mpol:  struct mempolicy to install
2140  *
2141  * Install non-NULL @mpol in inode's shared policy rb-tree.
2142  * On entry, the current task has a reference on a non-NULL @mpol.
2143  * This must be released on exit.
2144  * This is called at get_inode() calls and we can use GFP_KERNEL.
2145  */
2146 void mpol_shared_policy_init(struct shared_policy *sp, struct mempolicy *mpol)
2147 {
2148         int ret;
2149
2150         sp->root = RB_ROOT;             /* empty tree == default mempolicy */
2151         spin_lock_init(&sp->lock);
2152
2153         if (mpol) {
2154                 struct vm_area_struct pvma;
2155                 struct mempolicy *new;
2156                 NODEMASK_SCRATCH(scratch);
2157
2158                 if (!scratch)
2159                         goto put_mpol;
2160                 /* contextualize the tmpfs mount point mempolicy */
2161                 new = mpol_new(mpol->mode, mpol->flags, &mpol->w.user_nodemask);
2162                 if (IS_ERR(new))
2163                         goto free_scratch; /* no valid nodemask intersection */
2164
2165                 task_lock(current);
2166                 ret = mpol_set_nodemask(new, &mpol->w.user_nodemask, scratch);
2167                 task_unlock(current);
2168                 if (ret)
2169                         goto put_new;
2170
2171                 /* Create pseudo-vma that contains just the policy */
2172                 memset(&pvma, 0, sizeof(struct vm_area_struct));
2173                 pvma.vm_end = TASK_SIZE;        /* policy covers entire file */
2174                 mpol_set_shared_policy(sp, &pvma, new); /* adds ref */
2175
2176 put_new:
2177                 mpol_put(new);                  /* drop initial ref */
2178 free_scratch:
2179                 NODEMASK_SCRATCH_FREE(scratch);
2180 put_mpol:
2181                 mpol_put(mpol); /* drop our incoming ref on sb mpol */
2182         }
2183 }
2184
2185 int mpol_set_shared_policy(struct shared_policy *info,
2186                         struct vm_area_struct *vma, struct mempolicy *npol)
2187 {
2188         int err;
2189         struct sp_node *new = NULL;
2190         unsigned long sz = vma_pages(vma);
2191
2192         pr_debug("set_shared_policy %lx sz %lu %d %d %lx\n",
2193                  vma->vm_pgoff,
2194                  sz, npol ? npol->mode : -1,
2195                  npol ? npol->flags : -1,
2196                  npol ? nodes_addr(npol->v.nodes)[0] : -1);
2197
2198         if (npol) {
2199                 new = sp_alloc(vma->vm_pgoff, vma->vm_pgoff + sz, npol);
2200                 if (!new)
2201                         return -ENOMEM;
2202         }
2203         err = shared_policy_replace(info, vma->vm_pgoff, vma->vm_pgoff+sz, new);
2204         if (err && new)
2205                 kmem_cache_free(sn_cache, new);
2206         return err;
2207 }
2208
2209 /* Free a backing policy store on inode delete. */
2210 void mpol_free_shared_policy(struct shared_policy *p)
2211 {
2212         struct sp_node *n;
2213         struct rb_node *next;
2214
2215         if (!p->root.rb_node)
2216                 return;
2217         spin_lock(&p->lock);
2218         next = rb_first(&p->root);
2219         while (next) {
2220                 n = rb_entry(next, struct sp_node, nd);
2221                 next = rb_next(&n->nd);
2222                 rb_erase(&n->nd, &p->root);
2223                 mpol_put(n->policy);
2224                 kmem_cache_free(sn_cache, n);
2225         }
2226         spin_unlock(&p->lock);
2227 }
2228
2229 /* assumes fs == KERNEL_DS */
2230 void __init numa_policy_init(void)
2231 {
2232         nodemask_t interleave_nodes;
2233         unsigned long largest = 0;
2234         int nid, prefer = 0;
2235
2236         policy_cache = kmem_cache_create("numa_policy",
2237                                          sizeof(struct mempolicy),
2238                                          0, SLAB_PANIC, NULL);
2239
2240         sn_cache = kmem_cache_create("shared_policy_node",
2241                                      sizeof(struct sp_node),
2242                                      0, SLAB_PANIC, NULL);
2243
2244         /*
2245          * Set interleaving policy for system init. Interleaving is only
2246          * enabled across suitably sized nodes (default is >= 16MB), or
2247          * fall back to the largest node if they're all smaller.
2248          */
2249         nodes_clear(interleave_nodes);
2250         for_each_node_state(nid, N_HIGH_MEMORY) {
2251                 unsigned long total_pages = node_present_pages(nid);
2252
2253                 /* Preserve the largest node */
2254                 if (largest < total_pages) {
2255                         largest = total_pages;
2256                         prefer = nid;
2257                 }
2258
2259                 /* Interleave this node? */
2260                 if ((total_pages << PAGE_SHIFT) >= (16 << 20))
2261                         node_set(nid, interleave_nodes);
2262         }
2263
2264         /* All too small, use the largest */
2265         if (unlikely(nodes_empty(interleave_nodes)))
2266                 node_set(prefer, interleave_nodes);
2267
2268         if (do_set_mempolicy(MPOL_INTERLEAVE, 0, &interleave_nodes))
2269                 printk("numa_policy_init: interleaving failed\n");
2270 }
2271
2272 /* Reset policy of current process to default */
2273 void numa_default_policy(void)
2274 {
2275         do_set_mempolicy(MPOL_DEFAULT, 0, NULL);
2276 }
2277
2278 /*
2279  * Parse and format mempolicy from/to strings
2280  */
2281
2282 /*
2283  * "local" is pseudo-policy:  MPOL_PREFERRED with MPOL_F_LOCAL flag
2284  * Used only for mpol_parse_str() and mpol_to_str()
2285  */
2286 #define MPOL_LOCAL MPOL_MAX
2287 static const char * const policy_modes[] =
2288 {
2289         [MPOL_DEFAULT]    = "default",
2290         [MPOL_PREFERRED]  = "prefer",
2291         [MPOL_BIND]       = "bind",
2292         [MPOL_INTERLEAVE] = "interleave",
2293         [MPOL_LOCAL]      = "local"
2294 };
2295
2296
2297 #ifdef CONFIG_TMPFS
2298 /**
2299  * mpol_parse_str - parse string to mempolicy
2300  * @str:  string containing mempolicy to parse
2301  * @mpol:  pointer to struct mempolicy pointer, returned on success.
2302  * @no_context:  flag whether to "contextualize" the mempolicy
2303  *
2304  * Format of input:
2305  *      <mode>[=<flags>][:<nodelist>]
2306  *
2307  * if @no_context is true, save the input nodemask in w.user_nodemask in
2308  * the returned mempolicy.  This will be used to "clone" the mempolicy in
2309  * a specific context [cpuset] at a later time.  Used to parse tmpfs mpol
2310  * mount option.  Note that if 'static' or 'relative' mode flags were
2311  * specified, the input nodemask will already have been saved.  Saving
2312  * it again is redundant, but safe.
2313  *
2314  * On success, returns 0, else 1
2315  */
2316 int mpol_parse_str(char *str, struct mempolicy **mpol, int no_context)
2317 {
2318         struct mempolicy *new = NULL;
2319         unsigned short mode;
2320         unsigned short uninitialized_var(mode_flags);
2321         nodemask_t nodes;
2322         char *nodelist = strchr(str, ':');
2323         char *flags = strchr(str, '=');
2324         int err = 1;
2325
2326         if (nodelist) {
2327                 /* NUL-terminate mode or flags string */
2328                 *nodelist++ = '\0';
2329                 if (nodelist_parse(nodelist, nodes))
2330                         goto out;
2331                 if (!nodes_subset(nodes, node_states[N_HIGH_MEMORY]))
2332                         goto out;
2333         } else
2334                 nodes_clear(nodes);
2335
2336         if (flags)
2337                 *flags++ = '\0';        /* terminate mode string */
2338
2339         for (mode = 0; mode <= MPOL_LOCAL; mode++) {
2340                 if (!strcmp(str, policy_modes[mode])) {
2341                         break;
2342                 }
2343         }
2344         if (mode > MPOL_LOCAL)
2345                 goto out;
2346
2347         switch (mode) {
2348         case MPOL_PREFERRED:
2349                 /*
2350                  * Insist on a nodelist of one node only
2351                  */
2352                 if (nodelist) {
2353                         char *rest = nodelist;
2354                         while (isdigit(*rest))
2355                                 rest++;
2356                         if (*rest)
2357                                 goto out;
2358                 }
2359                 break;
2360         case MPOL_INTERLEAVE:
2361                 /*
2362                  * Default to online nodes with memory if no nodelist
2363                  */
2364                 if (!nodelist)
2365                         nodes = node_states[N_HIGH_MEMORY];
2366                 break;
2367         case MPOL_LOCAL:
2368                 /*
2369                  * Don't allow a nodelist;  mpol_new() checks flags
2370                  */
2371                 if (nodelist)
2372                         goto out;
2373                 mode = MPOL_PREFERRED;
2374                 break;
2375         case MPOL_DEFAULT:
2376                 /*
2377                  * Insist on a empty nodelist
2378                  */
2379                 if (!nodelist)
2380                         err = 0;
2381                 goto out;
2382         case MPOL_BIND:
2383                 /*
2384                  * Insist on a nodelist
2385                  */
2386                 if (!nodelist)
2387                         goto out;
2388         }
2389
2390         mode_flags = 0;
2391         if (flags) {
2392                 /*
2393                  * Currently, we only support two mutually exclusive
2394                  * mode flags.
2395                  */
2396                 if (!strcmp(flags, "static"))
2397                         mode_flags |= MPOL_F_STATIC_NODES;
2398                 else if (!strcmp(flags, "relative"))
2399                         mode_flags |= MPOL_F_RELATIVE_NODES;
2400                 else
2401                         goto out;
2402         }
2403
2404         new = mpol_new(mode, mode_flags, &nodes);
2405         if (IS_ERR(new))
2406                 goto out;
2407
2408         if (no_context) {
2409                 /* save for contextualization */
2410                 new->w.user_nodemask = nodes;
2411         } else {
2412                 int ret;
2413                 NODEMASK_SCRATCH(scratch);
2414                 if (scratch) {
2415                         task_lock(current);
2416                         ret = mpol_set_nodemask(new, &nodes, scratch);
2417                         task_unlock(current);
2418                 } else
2419                         ret = -ENOMEM;
2420                 NODEMASK_SCRATCH_FREE(scratch);
2421                 if (ret) {
2422                         mpol_put(new);
2423                         goto out;
2424                 }
2425         }
2426         err = 0;
2427
2428 out:
2429         /* Restore string for error message */
2430         if (nodelist)
2431                 *--nodelist = ':';
2432         if (flags)
2433                 *--flags = '=';
2434         if (!err)
2435                 *mpol = new;
2436         return err;
2437 }
2438 #endif /* CONFIG_TMPFS */
2439
2440 /**
2441  * mpol_to_str - format a mempolicy structure for printing
2442  * @buffer:  to contain formatted mempolicy string
2443  * @maxlen:  length of @buffer
2444  * @pol:  pointer to mempolicy to be formatted
2445  * @no_context:  "context free" mempolicy - use nodemask in w.user_nodemask
2446  *
2447  * Convert a mempolicy into a string.
2448  * Returns the number of characters in buffer (if positive)
2449  * or an error (negative)
2450  */
2451 int mpol_to_str(char *buffer, int maxlen, struct mempolicy *pol, int no_context)
2452 {
2453         char *p = buffer;
2454         int l;
2455         nodemask_t nodes;
2456         unsigned short mode;
2457         unsigned short flags = pol ? pol->flags : 0;
2458
2459         /*
2460          * Sanity check:  room for longest mode, flag and some nodes
2461          */
2462         VM_BUG_ON(maxlen < strlen("interleave") + strlen("relative") + 16);
2463
2464         if (!pol || pol == &default_policy)
2465                 mode = MPOL_DEFAULT;
2466         else
2467                 mode = pol->mode;
2468
2469         switch (mode) {
2470         case MPOL_DEFAULT:
2471                 nodes_clear(nodes);
2472                 break;
2473
2474         case MPOL_PREFERRED:
2475                 nodes_clear(nodes);
2476                 if (flags & MPOL_F_LOCAL)
2477                         mode = MPOL_LOCAL;      /* pseudo-policy */
2478                 else
2479                         node_set(pol->v.preferred_node, nodes);
2480                 break;
2481
2482         case MPOL_BIND:
2483                 /* Fall through */
2484         case MPOL_INTERLEAVE:
2485                 if (no_context)
2486                         nodes = pol->w.user_nodemask;
2487                 else
2488                         nodes = pol->v.nodes;
2489                 break;
2490
2491         default:
2492                 BUG();
2493         }
2494
2495         l = strlen(policy_modes[mode]);
2496         if (buffer + maxlen < p + l + 1)
2497                 return -ENOSPC;
2498
2499         strcpy(p, policy_modes[mode]);
2500         p += l;
2501
2502         if (flags & MPOL_MODE_FLAGS) {
2503                 if (buffer + maxlen < p + 2)
2504                         return -ENOSPC;
2505                 *p++ = '=';
2506
2507                 /*
2508                  * Currently, the only defined flags are mutually exclusive
2509                  */
2510                 if (flags & MPOL_F_STATIC_NODES)
2511                         p += snprintf(p, buffer + maxlen - p, "static");
2512                 else if (flags & MPOL_F_RELATIVE_NODES)
2513                         p += snprintf(p, buffer + maxlen - p, "relative");
2514         }
2515
2516         if (!nodes_empty(nodes)) {
2517                 if (buffer + maxlen < p + 2)
2518                         return -ENOSPC;
2519                 *p++ = ':';
2520                 p += nodelist_scnprintf(p, buffer + maxlen - p, nodes);
2521         }
2522         return p - buffer;
2523 }
2524
2525 struct numa_maps {
2526         unsigned long pages;
2527         unsigned long anon;
2528         unsigned long active;
2529         unsigned long writeback;
2530         unsigned long mapcount_max;
2531         unsigned long dirty;
2532         unsigned long swapcache;
2533         unsigned long node[MAX_NUMNODES];
2534 };
2535
2536 static void gather_stats(struct page *page, void *private, int pte_dirty)
2537 {
2538         struct numa_maps *md = private;
2539         int count = page_mapcount(page);
2540
2541         md->pages++;
2542         if (pte_dirty || PageDirty(page))
2543                 md->dirty++;
2544
2545         if (PageSwapCache(page))
2546                 md->swapcache++;
2547
2548         if (PageActive(page) || PageUnevictable(page))
2549                 md->active++;
2550
2551         if (PageWriteback(page))
2552                 md->writeback++;
2553
2554         if (PageAnon(page))
2555                 md->anon++;
2556
2557         if (count > md->mapcount_max)
2558                 md->mapcount_max = count;
2559
2560         md->node[page_to_nid(page)]++;
2561 }
2562
2563 #ifdef CONFIG_HUGETLB_PAGE
2564 static void check_huge_range(struct vm_area_struct *vma,
2565                 unsigned long start, unsigned long end,
2566                 struct numa_maps *md)
2567 {
2568         unsigned long addr;
2569         struct page *page;
2570         struct hstate *h = hstate_vma(vma);
2571         unsigned long sz = huge_page_size(h);
2572
2573         for (addr = start; addr < end; addr += sz) {
2574                 pte_t *ptep = huge_pte_offset(vma->vm_mm,
2575                                                 addr & huge_page_mask(h));
2576                 pte_t pte;
2577
2578                 if (!ptep)
2579                         continue;
2580
2581                 pte = *ptep;
2582                 if (pte_none(pte))
2583                         continue;
2584
2585                 page = pte_page(pte);
2586                 if (!page)
2587                         continue;
2588
2589                 gather_stats(page, md, pte_dirty(*ptep));
2590         }
2591 }
2592 #else
2593 static inline void check_huge_range(struct vm_area_struct *vma,
2594                 unsigned long start, unsigned long end,
2595                 struct numa_maps *md)
2596 {
2597 }
2598 #endif
2599
2600 /*
2601  * Display pages allocated per node and memory policy via /proc.
2602  */
2603 int show_numa_map(struct seq_file *m, void *v)
2604 {
2605         struct proc_maps_private *priv = m->private;
2606         struct vm_area_struct *vma = v;
2607         struct numa_maps *md;
2608         struct file *file = vma->vm_file;
2609         struct mm_struct *mm = vma->vm_mm;
2610         struct mempolicy *pol;
2611         int n;
2612         char buffer[50];
2613
2614         if (!mm)
2615                 return 0;
2616
2617         md = kzalloc(sizeof(struct numa_maps), GFP_KERNEL);
2618         if (!md)
2619                 return 0;
2620
2621         pol = get_vma_policy(priv->task, vma, vma->vm_start);
2622         mpol_to_str(buffer, sizeof(buffer), pol, 0);
2623         mpol_cond_put(pol);
2624
2625         seq_printf(m, "%08lx %s", vma->vm_start, buffer);
2626
2627         if (file) {
2628                 seq_printf(m, " file=");
2629                 seq_path(m, &file->f_path, "\n\t= ");
2630         } else if (vma->vm_start <= mm->brk && vma->vm_end >= mm->start_brk) {
2631                 seq_printf(m, " heap");
2632         } else if (vma->vm_start <= mm->start_stack &&
2633                         vma->vm_end >= mm->start_stack) {
2634                 seq_printf(m, " stack");
2635         }
2636
2637         if (is_vm_hugetlb_page(vma)) {
2638                 check_huge_range(vma, vma->vm_start, vma->vm_end, md);
2639                 seq_printf(m, " huge");
2640         } else {
2641                 check_pgd_range(vma, vma->vm_start, vma->vm_end,
2642                         &node_states[N_HIGH_MEMORY], MPOL_MF_STATS, md);
2643         }
2644
2645         if (!md->pages)
2646                 goto out;
2647
2648         if (md->anon)
2649                 seq_printf(m," anon=%lu",md->anon);
2650
2651         if (md->dirty)
2652                 seq_printf(m," dirty=%lu",md->dirty);
2653
2654         if (md->pages != md->anon && md->pages != md->dirty)
2655                 seq_printf(m, " mapped=%lu", md->pages);
2656
2657         if (md->mapcount_max > 1)
2658                 seq_printf(m, " mapmax=%lu", md->mapcount_max);
2659
2660         if (md->swapcache)
2661                 seq_printf(m," swapcache=%lu", md->swapcache);
2662
2663         if (md->active < md->pages && !is_vm_hugetlb_page(vma))
2664                 seq_printf(m," active=%lu", md->active);
2665
2666         if (md->writeback)
2667                 seq_printf(m," writeback=%lu", md->writeback);
2668
2669         for_each_node_state(n, N_HIGH_MEMORY)
2670                 if (md->node[n])
2671                         seq_printf(m, " N%d=%lu", n, md->node[n]);
2672 out:
2673         seq_putc(m, '\n');
2674         kfree(md);
2675
2676         if (m->count < m->size)
2677                 m->version = (vma != priv->tail_vma) ? vma->vm_start : 0;
2678         return 0;
2679 }