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 *, int pte_dirty);
 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, pte_dirty(*pte));
 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_NICE))
 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_NICE)) {
 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_NICE)) {
 953                 err = -EPERM;
 954                 goto out;
 955         }
 956
 957         err = do_migrate_pages(mm, &old, &new,
 958                 capable(CAP_SYS_NICE) ? MPOL_MF_MOVE_ALL : MPOL_MF_MOVE);
 959 out:
 960         mmput(mm);
 961         return err;
 962 }
 963
 964
 965 /* Retrieve NUMA policy */
 966 asmlinkage long sys_get_mempolicy(int __user *policy,
 967                                 unsigned long __user *nmask,
 968                                 unsigned long maxnode,
 969                                 unsigned long addr, unsigned long flags)
 970 {
 971         int err, pval;
 972         nodemask_t nodes;
 973
 974         if (nmask != NULL && maxnode < MAX_NUMNODES)
 975                 return -EINVAL;
 976
 977         err = do_get_mempolicy(&pval, &nodes, addr, flags);
 978
 979         if (err)
 980                 return err;
 981
 982         if (policy && put_user(pval, policy))
 983                 return -EFAULT;
 984
 985         if (nmask)
 986                 err = copy_nodes_to_user(nmask, maxnode, &nodes);
 987
 988         return err;
 989 }
 990
 991 #ifdef CONFIG_COMPAT
 992
 993 asmlinkage long compat_sys_get_mempolicy(int __user *policy,
 994                                      compat_ulong_t __user *nmask,
 995                                      compat_ulong_t maxnode,
 996                                      compat_ulong_t addr, compat_ulong_t flags)
 997 {
 998         long err;
 999         unsigned long __user *nm = NULL;
1000         unsigned long nr_bits, alloc_size;
1001         DECLARE_BITMAP(bm, MAX_NUMNODES);
1002
1003         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1004         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1005
1006         if (nmask)
1007                 nm = compat_alloc_user_space(alloc_size);
1008
1009         err = sys_get_mempolicy(policy, nm, nr_bits+1, addr, flags);
1010
1011         if (!err && nmask) {
1012                 err = copy_from_user(bm, nm, alloc_size);
1013                 /* ensure entire bitmap is zeroed */
1014                 err |= clear_user(nmask, ALIGN(maxnode-1, 8) / 8);
1015                 err |= compat_put_bitmap(nmask, bm, nr_bits);
1016         }
1017
1018         return err;
1019 }
1020
1021 asmlinkage long compat_sys_set_mempolicy(int mode, compat_ulong_t __user *nmask,
1022                                      compat_ulong_t maxnode)
1023 {
1024         long err = 0;
1025         unsigned long __user *nm = NULL;
1026         unsigned long nr_bits, alloc_size;
1027         DECLARE_BITMAP(bm, MAX_NUMNODES);
1028
1029         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1030         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1031
1032         if (nmask) {
1033                 err = compat_get_bitmap(bm, nmask, nr_bits);
1034                 nm = compat_alloc_user_space(alloc_size);
1035                 err |= copy_to_user(nm, bm, alloc_size);
1036         }
1037
1038         if (err)
1039                 return -EFAULT;
1040
1041         return sys_set_mempolicy(mode, nm, nr_bits+1);
1042 }
1043
1044 asmlinkage long compat_sys_mbind(compat_ulong_t start, compat_ulong_t len,
1045                              compat_ulong_t mode, compat_ulong_t __user *nmask,
1046                              compat_ulong_t maxnode, compat_ulong_t flags)
1047 {
1048         long err = 0;
1049         unsigned long __user *nm = NULL;
1050         unsigned long nr_bits, alloc_size;
1051         nodemask_t bm;
1052
1053         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
1054         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
1055
1056         if (nmask) {
1057                 err = compat_get_bitmap(nodes_addr(bm), nmask, nr_bits);
1058                 nm = compat_alloc_user_space(alloc_size);
1059                 err |= copy_to_user(nm, nodes_addr(bm), alloc_size);
1060         }
1061
1062         if (err)
1063                 return -EFAULT;
1064
1065         return sys_mbind(start, len, mode, nm, nr_bits+1, flags);
1066 }
1067
1068 #endif
1069
1070 /* Return effective policy for a VMA */
1071 static struct mempolicy * get_vma_policy(struct task_struct *task,
1072                 struct vm_area_struct *vma, unsigned long addr)
1073 {
1074         struct mempolicy *pol = task->mempolicy;
1075
1076         if (vma) {
1077                 if (vma->vm_ops && vma->vm_ops->get_policy)
1078                         pol = vma->vm_ops->get_policy(vma, addr);
1079                 else if (vma->vm_policy &&
1080                                 vma->vm_policy->policy != MPOL_DEFAULT)
1081                         pol = vma->vm_policy;
1082         }
1083         if (!pol)
1084                 pol = &default_policy;
1085         return pol;
1086 }
1087
1088 /* Return a zonelist representing a mempolicy */
1089 static struct zonelist *zonelist_policy(gfp_t gfp, struct mempolicy *policy)
1090 {
1091         int nd;
1092
1093         switch (policy->policy) {
1094         case MPOL_PREFERRED:
1095                 nd = policy->v.preferred_node;
1096                 if (nd < 0)
1097                         nd = numa_node_id();
1098                 break;
1099         case MPOL_BIND:
1100                 /* Lower zones don't get a policy applied */
1101                 /* Careful: current->mems_allowed might have moved */
1102                 if (gfp_zone(gfp) >= policy_zone)
1103                         if (cpuset_zonelist_valid_mems_allowed(policy->v.zonelist))
1104                                 return policy->v.zonelist;
1105                 /*FALL THROUGH*/
1106         case MPOL_INTERLEAVE: /* should not happen */
1107         case MPOL_DEFAULT:
1108                 nd = numa_node_id();
1109                 break;
1110         default:
1111                 nd = 0;
1112                 BUG();
1113         }
1114         return NODE_DATA(nd)->node_zonelists + gfp_zone(gfp);
1115 }
1116
1117 /* Do dynamic interleaving for a process */
1118 static unsigned interleave_nodes(struct mempolicy *policy)
1119 {
1120         unsigned nid, next;
1121         struct task_struct *me = current;
1122
1123         nid = me->il_next;
1124         next = next_node(nid, policy->v.nodes);
1125         if (next >= MAX_NUMNODES)
1126                 next = first_node(policy->v.nodes);
1127         me->il_next = next;
1128         return nid;
1129 }
1130
1131 /*
1132  * Depending on the memory policy provide a node from which to allocate the
1133  * next slab entry.
1134  */
1135 unsigned slab_node(struct mempolicy *policy)
1136 {
1137         switch (policy->policy) {
1138         case MPOL_INTERLEAVE:
1139                 return interleave_nodes(policy);
1140
1141         case MPOL_BIND:
1142                 /*
1143                  * Follow bind policy behavior and start allocation at the
1144                  * first node.
1145                  */
1146                 return policy->v.zonelist->zones[0]->zone_pgdat->node_id;
1147
1148         case MPOL_PREFERRED:
1149                 if (policy->v.preferred_node >= 0)
1150                         return policy->v.preferred_node;
1151                 /* Fall through */
1152
1153         default:
1154                 return numa_node_id();
1155         }
1156 }
1157
1158 /* Do static interleaving for a VMA with known offset. */
1159 static unsigned offset_il_node(struct mempolicy *pol,
1160                 struct vm_area_struct *vma, unsigned long off)
1161 {
1162         unsigned nnodes = nodes_weight(pol->v.nodes);
1163         unsigned target = (unsigned)off % nnodes;
1164         int c;
1165         int nid = -1;
1166
1167         c = 0;
1168         do {
1169                 nid = next_node(nid, pol->v.nodes);
1170                 c++;
1171         } while (c <= target);
1172         return nid;
1173 }
1174
1175 /* Determine a node number for interleave */
1176 static inline unsigned interleave_nid(struct mempolicy *pol,
1177                  struct vm_area_struct *vma, unsigned long addr, int shift)
1178 {
1179         if (vma) {
1180                 unsigned long off;
1181
1182                 off = vma->vm_pgoff;
1183                 off += (addr - vma->vm_start) >> shift;
1184                 return offset_il_node(pol, vma, off);
1185         } else
1186                 return interleave_nodes(pol);
1187 }
1188
1189 #ifdef CONFIG_HUGETLBFS
1190 /* Return a zonelist suitable for a huge page allocation. */
1191 struct zonelist *huge_zonelist(struct vm_area_struct *vma, unsigned long addr)
1192 {
1193         struct mempolicy *pol = get_vma_policy(current, vma, addr);
1194
1195         if (pol->policy == MPOL_INTERLEAVE) {
1196                 unsigned nid;
1197
1198                 nid = interleave_nid(pol, vma, addr, HPAGE_SHIFT);
1199                 return NODE_DATA(nid)->node_zonelists + gfp_zone(GFP_HIGHUSER);
1200         }
1201         return zonelist_policy(GFP_HIGHUSER, pol);
1202 }
1203 #endif
1204
1205 /* Allocate a page in interleaved policy.
1206    Own path because it needs to do special accounting. */
1207 static struct page *alloc_page_interleave(gfp_t gfp, unsigned order,
1208                                         unsigned nid)
1209 {
1210         struct zonelist *zl;
1211         struct page *page;
1212
1213         zl = NODE_DATA(nid)->node_zonelists + gfp_zone(gfp);
1214         page = __alloc_pages(gfp, order, zl);
1215         if (page && page_zone(page) == zl->zones[0]) {
1216                 zone_pcp(zl->zones[0],get_cpu())->interleave_hit++;
1217                 put_cpu();
1218         }
1219         return page;
1220 }
1221
1222 /**
1223  *      alloc_page_vma  - Allocate a page for a VMA.
1224  *
1225  *      @gfp:
1226  *      %GFP_USER    user allocation.
1227  *      %GFP_KERNEL  kernel allocations,
1228  *      %GFP_HIGHMEM highmem/user allocations,
1229  *      %GFP_FS      allocation should not call back into a file system.
1230  *      %GFP_ATOMIC  don't sleep.
1231  *
1232  *      @vma:  Pointer to VMA or NULL if not available.
1233  *      @addr: Virtual Address of the allocation. Must be inside the VMA.
1234  *
1235  *      This function allocates a page from the kernel page pool and applies
1236  *      a NUMA policy associated with the VMA or the current process.
1237  *      When VMA is not NULL caller must hold down_read on the mmap_sem of the
1238  *      mm_struct of the VMA to prevent it from going away. Should be used for
1239  *      all allocations for pages that will be mapped into
1240  *      user space. Returns NULL when no page can be allocated.
1241  *
1242  *      Should be called with the mm_sem of the vma hold.
1243  */
1244 struct page *
1245 alloc_page_vma(gfp_t gfp, struct vm_area_struct *vma, unsigned long addr)
1246 {
1247         struct mempolicy *pol = get_vma_policy(current, vma, addr);
1248
1249         cpuset_update_task_memory_state();
1250
1251         if (unlikely(pol->policy == MPOL_INTERLEAVE)) {
1252                 unsigned nid;
1253
1254                 nid = interleave_nid(pol, vma, addr, PAGE_SHIFT);
1255                 return alloc_page_interleave(gfp, 0, nid);
1256         }
1257         return __alloc_pages(gfp, 0, zonelist_policy(gfp, pol));
1258 }
1259
1260 /**
1261  *      alloc_pages_current - Allocate pages.
1262  *
1263  *      @gfp:
1264  *              %GFP_USER   user allocation,
1265  *              %GFP_KERNEL kernel allocation,
1266  *              %GFP_HIGHMEM highmem allocation,
1267  *              %GFP_FS     don't call back into a file system.
1268  *              %GFP_ATOMIC don't sleep.
1269  *      @order: Power of two of allocation size in pages. 0 is a single page.
1270  *
1271  *      Allocate a page from the kernel page pool.  When not in
1272  *      interrupt context and apply the current process NUMA policy.
1273  *      Returns NULL when no page can be allocated.
1274  *
1275  *      Don't call cpuset_update_task_memory_state() unless
1276  *      1) it's ok to take cpuset_sem (can WAIT), and
1277  *      2) allocating for current task (not interrupt).
1278  */
1279 struct page *alloc_pages_current(gfp_t gfp, unsigned order)
1280 {
1281         struct mempolicy *pol = current->mempolicy;
1282
1283         if ((gfp & __GFP_WAIT) && !in_interrupt())
1284                 cpuset_update_task_memory_state();
1285         if (!pol || in_interrupt())
1286                 pol = &default_policy;
1287         if (pol->policy == MPOL_INTERLEAVE)
1288                 return alloc_page_interleave(gfp, order, interleave_nodes(pol));
1289         return __alloc_pages(gfp, order, zonelist_policy(gfp, pol));
1290 }
1291 EXPORT_SYMBOL(alloc_pages_current);
1292
1293 /*
1294  * If mpol_copy() sees current->cpuset == cpuset_being_rebound, then it
1295  * rebinds the mempolicy its copying by calling mpol_rebind_policy()
1296  * with the mems_allowed returned by cpuset_mems_allowed().  This
1297  * keeps mempolicies cpuset relative after its cpuset moves.  See
1298  * further kernel/cpuset.c update_nodemask().
1299  */
1300 void *cpuset_being_rebound;
1301
1302 /* Slow path of a mempolicy copy */
1303 struct mempolicy *__mpol_copy(struct mempolicy *old)
1304 {
1305         struct mempolicy *new = kmem_cache_alloc(policy_cache, GFP_KERNEL);
1306
1307         if (!new)
1308                 return ERR_PTR(-ENOMEM);
1309         if (current_cpuset_is_being_rebound()) {
1310                 nodemask_t mems = cpuset_mems_allowed(current);
1311                 mpol_rebind_policy(old, &mems);
1312         }
1313         *new = *old;
1314         atomic_set(&new->refcnt, 1);
1315         if (new->policy == MPOL_BIND) {
1316                 int sz = ksize(old->v.zonelist);
1317                 new->v.zonelist = kmalloc(sz, SLAB_KERNEL);
1318                 if (!new->v.zonelist) {
1319                         kmem_cache_free(policy_cache, new);
1320                         return ERR_PTR(-ENOMEM);
1321                 }
1322                 memcpy(new->v.zonelist, old->v.zonelist, sz);
1323         }
1324         return new;
1325 }
1326
1327 /* Slow path of a mempolicy comparison */
1328 int __mpol_equal(struct mempolicy *a, struct mempolicy *b)
1329 {
1330         if (!a || !b)
1331                 return 0;
1332         if (a->policy != b->policy)
1333                 return 0;
1334         switch (a->policy) {
1335         case MPOL_DEFAULT:
1336                 return 1;
1337         case MPOL_INTERLEAVE:
1338                 return nodes_equal(a->v.nodes, b->v.nodes);
1339         case MPOL_PREFERRED:
1340                 return a->v.preferred_node == b->v.preferred_node;
1341         case MPOL_BIND: {
1342                 int i;
1343                 for (i = 0; a->v.zonelist->zones[i]; i++)
1344                         if (a->v.zonelist->zones[i] != b->v.zonelist->zones[i])
1345                                 return 0;
1346                 return b->v.zonelist->zones[i] == NULL;
1347         }
1348         default:
1349                 BUG();
1350                 return 0;
1351         }
1352 }
1353
1354 /* Slow path of a mpol destructor. */
1355 void __mpol_free(struct mempolicy *p)
1356 {
1357         if (!atomic_dec_and_test(&p->refcnt))
1358                 return;
1359         if (p->policy == MPOL_BIND)
1360                 kfree(p->v.zonelist);
1361         p->policy = MPOL_DEFAULT;
1362         kmem_cache_free(policy_cache, p);
1363 }
1364
1365 /*
1366  * Shared memory backing store policy support.
1367  *
1368  * Remember policies even when nobody has shared memory mapped.
1369  * The policies are kept in Red-Black tree linked from the inode.
1370  * They are protected by the sp->lock spinlock, which should be held
1371  * for any accesses to the tree.
1372  */
1373
1374 /* lookup first element intersecting start-end */
1375 /* Caller holds sp->lock */
1376 static struct sp_node *
1377 sp_lookup(struct shared_policy *sp, unsigned long start, unsigned long end)
1378 {
1379         struct rb_node *n = sp->root.rb_node;
1380
1381         while (n) {
1382                 struct sp_node *p = rb_entry(n, struct sp_node, nd);
1383
1384                 if (start >= p->end)
1385                         n = n->rb_right;
1386                 else if (end <= p->start)
1387                         n = n->rb_left;
1388                 else
1389                         break;
1390         }
1391         if (!n)
1392                 return NULL;
1393         for (;;) {
1394                 struct sp_node *w = NULL;
1395                 struct rb_node *prev = rb_prev(n);
1396                 if (!prev)
1397                         break;
1398                 w = rb_entry(prev, struct sp_node, nd);
1399                 if (w->end <= start)
1400                         break;
1401                 n = prev;
1402         }
1403         return rb_entry(n, struct sp_node, nd);
1404 }
1405
1406 /* Insert a new shared policy into the list. */
1407 /* Caller holds sp->lock */
1408 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
1409 {
1410         struct rb_node **p = &sp->root.rb_node;
1411         struct rb_node *parent = NULL;
1412         struct sp_node *nd;
1413
1414         while (*p) {
1415                 parent = *p;
1416                 nd = rb_entry(parent, struct sp_node, nd);
1417                 if (new->start < nd->start)
1418                         p = &(*p)->rb_left;
1419                 else if (new->end > nd->end)
1420                         p = &(*p)->rb_right;
1421                 else
1422                         BUG();
1423         }
1424         rb_link_node(&new->nd, parent, p);
1425         rb_insert_color(&new->nd, &sp->root);
1426         PDprintk("inserting %lx-%lx: %d\n", new->start, new->end,
1427                  new->policy ? new->policy->policy : 0);
1428 }
1429
1430 /* Find shared policy intersecting idx */
1431 struct mempolicy *
1432 mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
1433 {
1434         struct mempolicy *pol = NULL;
1435         struct sp_node *sn;
1436
1437         if (!sp->root.rb_node)
1438                 return NULL;
1439         spin_lock(&sp->lock);
1440         sn = sp_lookup(sp, idx, idx+1);
1441         if (sn) {
1442                 mpol_get(sn->policy);
1443                 pol = sn->policy;
1444         }
1445         spin_unlock(&sp->lock);
1446         return pol;
1447 }
1448
1449 static void sp_delete(struct shared_policy *sp, struct sp_node *n)
1450 {
1451         PDprintk("deleting %lx-l%x\n", n->start, n->end);
1452         rb_erase(&n->nd, &sp->root);
1453         mpol_free(n->policy);
1454         kmem_cache_free(sn_cache, n);
1455 }
1456
1457 struct sp_node *
1458 sp_alloc(unsigned long start, unsigned long end, struct mempolicy *pol)
1459 {
1460         struct sp_node *n = kmem_cache_alloc(sn_cache, GFP_KERNEL);
1461
1462         if (!n)
1463                 return NULL;
1464         n->start = start;
1465         n->end = end;
1466         mpol_get(pol);
1467         n->policy = pol;
1468         return n;
1469 }
1470
1471 /* Replace a policy range. */
1472 static int shared_policy_replace(struct shared_policy *sp, unsigned long start,
1473                                  unsigned long end, struct sp_node *new)
1474 {
1475         struct sp_node *n, *new2 = NULL;
1476
1477 restart:
1478         spin_lock(&sp->lock);
1479         n = sp_lookup(sp, start, end);
1480         /* Take care of old policies in the same range. */
1481         while (n && n->start < end) {
1482                 struct rb_node *next = rb_next(&n->nd);
1483                 if (n->start >= start) {
1484                         if (n->end <= end)
1485                                 sp_delete(sp, n);
1486                         else
1487                                 n->start = end;
1488                 } else {
1489                         /* Old policy spanning whole new range. */
1490                         if (n->end > end) {
1491                                 if (!new2) {
1492                                         spin_unlock(&sp->lock);
1493                                         new2 = sp_alloc(end, n->end, n->policy);
1494                                         if (!new2)
1495                                                 return -ENOMEM;
1496                                         goto restart;
1497                                 }
1498                                 n->end = start;
1499                                 sp_insert(sp, new2);
1500                                 new2 = NULL;
1501                                 break;
1502                         } else
1503                                 n->end = start;
1504                 }
1505                 if (!next)
1506                         break;
1507                 n = rb_entry(next, struct sp_node, nd);
1508         }
1509         if (new)
1510                 sp_insert(sp, new);
1511         spin_unlock(&sp->lock);
1512         if (new2) {
1513                 mpol_free(new2->policy);
1514                 kmem_cache_free(sn_cache, new2);
1515         }
1516         return 0;
1517 }
1518
1519 void mpol_shared_policy_init(struct shared_policy *info, int policy,
1520                                 nodemask_t *policy_nodes)
1521 {
1522         info->root = RB_ROOT;
1523         spin_lock_init(&info->lock);
1524
1525         if (policy != MPOL_DEFAULT) {
1526                 struct mempolicy *newpol;
1527
1528                 /* Falls back to MPOL_DEFAULT on any error */
1529                 newpol = mpol_new(policy, policy_nodes);
1530                 if (!IS_ERR(newpol)) {
1531                         /* Create pseudo-vma that contains just the policy */
1532                         struct vm_area_struct pvma;
1533
1534                         memset(&pvma, 0, sizeof(struct vm_area_struct));
1535                         /* Policy covers entire file */
1536                         pvma.vm_end = TASK_SIZE;
1537                         mpol_set_shared_policy(info, &pvma, newpol);
1538                         mpol_free(newpol);
1539                 }
1540         }
1541 }
1542
1543 int mpol_set_shared_policy(struct shared_policy *info,
1544                         struct vm_area_struct *vma, struct mempolicy *npol)
1545 {
1546         int err;
1547         struct sp_node *new = NULL;
1548         unsigned long sz = vma_pages(vma);
1549
1550         PDprintk("set_shared_policy %lx sz %lu %d %lx\n",
1551                  vma->vm_pgoff,
1552                  sz, npol? npol->policy : -1,
1553                 npol ? nodes_addr(npol->v.nodes)[0] : -1);
1554
1555         if (npol) {
1556                 new = sp_alloc(vma->vm_pgoff, vma->vm_pgoff + sz, npol);
1557                 if (!new)
1558                         return -ENOMEM;
1559         }
1560         err = shared_policy_replace(info, vma->vm_pgoff, vma->vm_pgoff+sz, new);
1561         if (err && new)
1562                 kmem_cache_free(sn_cache, new);
1563         return err;
1564 }
1565
1566 /* Free a backing policy store on inode delete. */
1567 void mpol_free_shared_policy(struct shared_policy *p)
1568 {
1569         struct sp_node *n;
1570         struct rb_node *next;
1571
1572         if (!p->root.rb_node)
1573                 return;
1574         spin_lock(&p->lock);
1575         next = rb_first(&p->root);
1576         while (next) {
1577                 n = rb_entry(next, struct sp_node, nd);
1578                 next = rb_next(&n->nd);
1579                 rb_erase(&n->nd, &p->root);
1580                 mpol_free(n->policy);
1581                 kmem_cache_free(sn_cache, n);
1582         }
1583         spin_unlock(&p->lock);
1584 }
1585
1586 /* assumes fs == KERNEL_DS */
1587 void __init numa_policy_init(void)
1588 {
1589         policy_cache = kmem_cache_create("numa_policy",
1590                                          sizeof(struct mempolicy),
1591                                          0, SLAB_PANIC, NULL, NULL);
1592
1593         sn_cache = kmem_cache_create("shared_policy_node",
1594                                      sizeof(struct sp_node),
1595                                      0, SLAB_PANIC, NULL, NULL);
1596
1597         /* Set interleaving policy for system init. This way not all
1598            the data structures allocated at system boot end up in node zero. */
1599
1600         if (do_set_mempolicy(MPOL_INTERLEAVE, &node_online_map))
1601                 printk("numa_policy_init: interleaving failed\n");
1602 }
1603
1604 /* Reset policy of current process to default */
1605 void numa_default_policy(void)
1606 {
1607         do_set_mempolicy(MPOL_DEFAULT, NULL);
1608 }
1609
1610 /* Migrate a policy to a different set of nodes */
1611 void mpol_rebind_policy(struct mempolicy *pol, const nodemask_t *newmask)
1612 {
1613         nodemask_t *mpolmask;
1614         nodemask_t tmp;
1615
1616         if (!pol)
1617                 return;
1618         mpolmask = &pol->cpuset_mems_allowed;
1619         if (nodes_equal(*mpolmask, *newmask))
1620                 return;
1621
1622         switch (pol->policy) {
1623         case MPOL_DEFAULT:
1624                 break;
1625         case MPOL_INTERLEAVE:
1626                 nodes_remap(tmp, pol->v.nodes, *mpolmask, *newmask);
1627                 pol->v.nodes = tmp;
1628                 *mpolmask = *newmask;
1629                 current->il_next = node_remap(current->il_next,
1630                                                 *mpolmask, *newmask);
1631                 break;
1632         case MPOL_PREFERRED:
1633                 pol->v.preferred_node = node_remap(pol->v.preferred_node,
1634                                                 *mpolmask, *newmask);
1635                 *mpolmask = *newmask;
1636                 break;
1637         case MPOL_BIND: {
1638                 nodemask_t nodes;
1639                 struct zone **z;
1640                 struct zonelist *zonelist;
1641
1642                 nodes_clear(nodes);
1643                 for (z = pol->v.zonelist->zones; *z; z++)
1644                         node_set((*z)->zone_pgdat->node_id, nodes);
1645                 nodes_remap(tmp, nodes, *mpolmask, *newmask);
1646                 nodes = tmp;
1647
1648                 zonelist = bind_zonelist(&nodes);
1649
1650                 /* If no mem, then zonelist is NULL and we keep old zonelist.
1651                  * If that old zonelist has no remaining mems_allowed nodes,
1652                  * then zonelist_policy() will "FALL THROUGH" to MPOL_DEFAULT.
1653                  */
1654
1655                 if (zonelist) {
1656                         /* Good - got mem - substitute new zonelist */
1657                         kfree(pol->v.zonelist);
1658                         pol->v.zonelist = zonelist;
1659                 }
1660                 *mpolmask = *newmask;
1661                 break;
1662         }
1663         default:
1664                 BUG();
1665                 break;
1666         }
1667 }
1668
1669 /*
1670  * Wrapper for mpol_rebind_policy() that just requires task
1671  * pointer, and updates task mempolicy.
1672  */
1673
1674 void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new)
1675 {
1676         mpol_rebind_policy(tsk->mempolicy, new);
1677 }
1678
1679 /*
1680  * Rebind each vma in mm to new nodemask.
1681  *
1682  * Call holding a reference to mm.  Takes mm->mmap_sem during call.
1683  */
1684
1685 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
1686 {
1687         struct vm_area_struct *vma;
1688
1689         down_write(&mm->mmap_sem);
1690         for (vma = mm->mmap; vma; vma = vma->vm_next)
1691                 mpol_rebind_policy(vma->vm_policy, new);
1692         up_write(&mm->mmap_sem);
1693 }
1694
1695 /*
1696  * Display pages allocated per node and memory policy via /proc.
1697  */
1698
1699 static const char *policy_types[] = { "default", "prefer", "bind",
1700                                       "interleave" };
1701
1702 /*
1703  * Convert a mempolicy into a string.
1704  * Returns the number of characters in buffer (if positive)
1705  * or an error (negative)
1706  */
1707 static inline int mpol_to_str(char *buffer, int maxlen, struct mempolicy *pol)
1708 {
1709         char *p = buffer;
1710         int l;
1711         nodemask_t nodes;
1712         int mode = pol ? pol->policy : MPOL_DEFAULT;
1713
1714         switch (mode) {
1715         case MPOL_DEFAULT:
1716                 nodes_clear(nodes);
1717                 break;
1718
1719         case MPOL_PREFERRED:
1720                 nodes_clear(nodes);
1721                 node_set(pol->v.preferred_node, nodes);
1722                 break;
1723
1724         case MPOL_BIND:
1725                 get_zonemask(pol, &nodes);
1726                 break;
1727
1728         case MPOL_INTERLEAVE:
1729                 nodes = pol->v.nodes;
1730                 break;
1731
1732         default:
1733                 BUG();
1734                 return -EFAULT;
1735         }
1736
1737         l = strlen(policy_types[mode]);
1738         if (buffer + maxlen < p + l + 1)
1739                 return -ENOSPC;
1740
1741         strcpy(p, policy_types[mode]);
1742         p += l;
1743
1744         if (!nodes_empty(nodes)) {
1745                 if (buffer + maxlen < p + 2)
1746                         return -ENOSPC;
1747                 *p++ = '=';
1748                 p += nodelist_scnprintf(p, buffer + maxlen - p, nodes);
1749         }
1750         return p - buffer;
1751 }
1752
1753 struct numa_maps {
1754         unsigned long pages;
1755         unsigned long anon;
1756         unsigned long active;
1757         unsigned long writeback;
1758         unsigned long mapcount_max;
1759         unsigned long dirty;
1760         unsigned long swapcache;
1761         unsigned long node[MAX_NUMNODES];
1762 };
1763
1764 static void gather_stats(struct page *page, void *private, int pte_dirty)
1765 {
1766         struct numa_maps *md = private;
1767         int count = page_mapcount(page);
1768
1769         md->pages++;
1770         if (pte_dirty || PageDirty(page))
1771                 md->dirty++;
1772
1773         if (PageSwapCache(page))
1774                 md->swapcache++;
1775
1776         if (PageActive(page))
1777                 md->active++;
1778
1779         if (PageWriteback(page))
1780                 md->writeback++;
1781
1782         if (PageAnon(page))
1783                 md->anon++;
1784
1785         if (count > md->mapcount_max)
1786                 md->mapcount_max = count;
1787
1788         md->node[page_to_nid(page)]++;
1789         cond_resched();
1790 }
1791
1792 #ifdef CONFIG_HUGETLB_PAGE
1793 static void check_huge_range(struct vm_area_struct *vma,
1794                 unsigned long start, unsigned long end,
1795                 struct numa_maps *md)
1796 {
1797         unsigned long addr;
1798         struct page *page;
1799
1800         for (addr = start; addr < end; addr += HPAGE_SIZE) {
1801                 pte_t *ptep = huge_pte_offset(vma->vm_mm, addr & HPAGE_MASK);
1802                 pte_t pte;
1803
1804                 if (!ptep)
1805                         continue;
1806
1807                 pte = *ptep;
1808                 if (pte_none(pte))
1809                         continue;
1810
1811                 page = pte_page(pte);
1812                 if (!page)
1813                         continue;
1814
1815                 gather_stats(page, md, pte_dirty(*ptep));
1816         }
1817 }
1818 #else
1819 static inline void check_huge_range(struct vm_area_struct *vma,
1820                 unsigned long start, unsigned long end,
1821                 struct numa_maps *md)
1822 {
1823 }
1824 #endif
1825
1826 int show_numa_map(struct seq_file *m, void *v)
1827 {
1828         struct task_struct *task = m->private;
1829         struct vm_area_struct *vma = v;
1830         struct numa_maps *md;
1831         struct file *file = vma->vm_file;
1832         struct mm_struct *mm = vma->vm_mm;
1833         int n;
1834         char buffer[50];
1835
1836         if (!mm)
1837                 return 0;
1838
1839         md = kzalloc(sizeof(struct numa_maps), GFP_KERNEL);
1840         if (!md)
1841                 return 0;
1842
1843         mpol_to_str(buffer, sizeof(buffer),
1844                         get_vma_policy(task, vma, vma->vm_start));
1845
1846         seq_printf(m, "%08lx %s", vma->vm_start, buffer);
1847
1848         if (file) {
1849                 seq_printf(m, " file=");
1850                 seq_path(m, file->f_vfsmnt, file->f_dentry, "\n\t= ");
1851         } else if (vma->vm_start <= mm->brk && vma->vm_end >= mm->start_brk) {
1852                 seq_printf(m, " heap");
1853         } else if (vma->vm_start <= mm->start_stack &&
1854                         vma->vm_end >= mm->start_stack) {
1855                 seq_printf(m, " stack");
1856         }
1857
1858         if (is_vm_hugetlb_page(vma)) {
1859                 check_huge_range(vma, vma->vm_start, vma->vm_end, md);
1860                 seq_printf(m, " huge");
1861         } else {
1862                 check_pgd_range(vma, vma->vm_start, vma->vm_end,
1863                                 &node_online_map, MPOL_MF_STATS, md);
1864         }
1865
1866         if (!md->pages)
1867                 goto out;
1868
1869         if (md->anon)
1870                 seq_printf(m," anon=%lu",md->anon);
1871
1872         if (md->dirty)
1873                 seq_printf(m," dirty=%lu",md->dirty);
1874
1875         if (md->pages != md->anon && md->pages != md->dirty)
1876                 seq_printf(m, " mapped=%lu", md->pages);
1877
1878         if (md->mapcount_max > 1)
1879                 seq_printf(m, " mapmax=%lu", md->mapcount_max);
1880
1881         if (md->swapcache)
1882                 seq_printf(m," swapcache=%lu", md->swapcache);
1883
1884         if (md->active < md->pages && !is_vm_hugetlb_page(vma))
1885                 seq_printf(m," active=%lu", md->active);
1886
1887         if (md->writeback)
1888                 seq_printf(m," writeback=%lu", md->writeback);
1889
1890         for_each_online_node(n)
1891                 if (md->node[n])
1892                         seq_printf(m, " N%d=%lu", n, md->node[n]);
1893 out:
1894         seq_putc(m, '\n');
1895         kfree(md);
1896
1897         if (m->count < m->size)
1898                 m->version = (vma != get_gate_vma(task)) ? vma->vm_start : 0;
1899         return 0;
1900 }
1901