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