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