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