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