mm/mempolicy.c

   1 /*
   2  * Simple NUMA memory policy for the Linux kernel.
   3  *
   4  * Copyright 2003,2004 Andi Kleen, SuSE Labs.
   5  * Subject to the GNU Public License, version 2.
   6  *
   7  * NUMA policy allows the user to give hints in which node(s) memory should
   8  * be allocated.
   9  *
  10  * Support four policies per VMA and per process:
  11  *
  12  * The VMA policy has priority over the process policy for a page fault.
  13  *
  14  * interleave     Allocate memory interleaved over a set of nodes,
  15  *                with normal fallback if it fails.
  16  *                For VMA based allocations this interleaves based on the
  17  *                offset into the backing object or offset into the mapping
  18  *                for anonymous memory. For process policy an process counter
  19  *                is used.
  20  * bind           Only allocate memory on a specific set of nodes,
  21  *                no fallback.
  22  * preferred       Try a specific node first before normal fallback.
  23  *                As a special case node -1 here means do the allocation
  24  *                on the local CPU. This is normally identical to default,
  25  *                but useful to set in a VMA when you have a non default
  26  *                process policy.
  27  * default        Allocate on the local node first, or when on a VMA
  28  *                use the process policy. This is what Linux always did
  29  *                in a NUMA aware kernel and still does by, ahem, default.
  30  *
  31  * The process policy is applied for most non interrupt memory allocations
  32  * in that process' context. Interrupts ignore the policies and always
  33  * try to allocate on the local CPU. The VMA policy is only applied for memory
  34  * allocations for a VMA in the VM.
  35  *
  36  * Currently there are a few corner cases in swapping where the policy
  37  * is not applied, but the majority should be handled. When process policy
  38  * is used it is not remembered over swap outs/swap ins.
  39  *
  40  * Only the highest zone in the zone hierarchy gets policied. Allocations
  41  * requesting a lower zone just use default policy. This implies that
  42  * on systems with highmem kernel lowmem allocation don't get policied.
  43  * Same with GFP_DMA allocations.
  44  *
  45  * For shmfs/tmpfs/hugetlbfs shared memory the policy is shared between
  46  * all users and remembered even when nobody has memory mapped.
  47  */
  48
  49 /* Notebook:
  50    fix mmap readahead to honour policy and enable policy for any page cache
  51    object
  52    statistics for bigpages
  53    global policy for page cache? currently it uses process policy. Requires
  54    first item above.
  55    handle mremap for shared memory (currently ignored for the policy)
  56    grows down?
  57    make bind policy root only? It can trigger oom much faster and the
  58    kernel is not always grateful with that.
  59    could replace all the switch()es with a mempolicy_ops structure.
  60 */
  61
  62 #include <linux/mempolicy.h>
  63 #include <linux/mm.h>
  64 #include <linux/highmem.h>
  65 #include <linux/hugetlb.h>
  66 #include <linux/kernel.h>
  67 #include <linux/sched.h>
  68 #include <linux/mm.h>
  69 #include <linux/nodemask.h>
  70 #include <linux/gfp.h>
  71 #include <linux/slab.h>
  72 #include <linux/string.h>
  73 #include <linux/module.h>
  74 #include <linux/interrupt.h>
  75 #include <linux/init.h>
  76 #include <linux/compat.h>
  77 #include <linux/mempolicy.h>
  78 #include <asm/tlbflush.h>
  79 #include <asm/uaccess.h>
  80
  81 static kmem_cache_t *policy_cache;
  82 static kmem_cache_t *sn_cache;
  83
  84 #define PDprintk(fmt...)
  85
  86 /* Highest zone. An specific allocation for a zone below that is not
  87    policied. */
  88 static int policy_zone;
  89
  90 static struct mempolicy default_policy = {
  91         .refcnt = ATOMIC_INIT(1), /* never free it */
  92         .policy = MPOL_DEFAULT,
  93 };
  94
  95 /* Check if all specified nodes are online */
  96 static int nodes_online(unsigned long *nodes)
  97 {
  98         DECLARE_BITMAP(online2, MAX_NUMNODES);
  99
 100         bitmap_copy(online2, nodes_addr(node_online_map), MAX_NUMNODES);
 101         if (bitmap_empty(online2, MAX_NUMNODES))
 102                 set_bit(0, online2);
 103         if (!bitmap_subset(nodes, online2, MAX_NUMNODES))
 104                 return -EINVAL;
 105         return 0;
 106 }
 107
 108 /* Do sanity checking on a policy */
 109 static int mpol_check_policy(int mode, unsigned long *nodes)
 110 {
 111         int empty = bitmap_empty(nodes, MAX_NUMNODES);
 112
 113         switch (mode) {
 114         case MPOL_DEFAULT:
 115                 if (!empty)
 116                         return -EINVAL;
 117                 break;
 118         case MPOL_BIND:
 119         case MPOL_INTERLEAVE:
 120                 /* Preferred will only use the first bit, but allow
 121                    more for now. */
 122                 if (empty)
 123                         return -EINVAL;
 124                 break;
 125         }
 126         return nodes_online(nodes);
 127 }
 128
 129 /* Copy a node mask from user space. */
 130 static int get_nodes(unsigned long *nodes, unsigned long __user *nmask,
 131                      unsigned long maxnode, int mode)
 132 {
 133         unsigned long k;
 134         unsigned long nlongs;
 135         unsigned long endmask;
 136
 137         --maxnode;
 138         bitmap_zero(nodes, MAX_NUMNODES);
 139         if (maxnode == 0 || !nmask)
 140                 return 0;
 141
 142         nlongs = BITS_TO_LONGS(maxnode);
 143         if ((maxnode % BITS_PER_LONG) == 0)
 144                 endmask = ~0UL;
 145         else
 146                 endmask = (1UL << (maxnode % BITS_PER_LONG)) - 1;
 147
 148         /* When the user specified more nodes than supported just check
 149            if the non supported part is all zero. */
 150         if (nlongs > BITS_TO_LONGS(MAX_NUMNODES)) {
 151                 if (nlongs > PAGE_SIZE/sizeof(long))
 152                         return -EINVAL;
 153                 for (k = BITS_TO_LONGS(MAX_NUMNODES); k < nlongs; k++) {
 154                         unsigned long t;
 155                         if (get_user(t,  nmask + k))
 156                                 return -EFAULT;
 157                         if (k == nlongs - 1) {
 158                                 if (t & endmask)
 159                                         return -EINVAL;
 160                         } else if (t)
 161                                 return -EINVAL;
 162                 }
 163                 nlongs = BITS_TO_LONGS(MAX_NUMNODES);
 164                 endmask = ~0UL;
 165         }
 166
 167         if (copy_from_user(nodes, nmask, nlongs*sizeof(unsigned long)))
 168                 return -EFAULT;
 169         nodes[nlongs-1] &= endmask;
 170         return mpol_check_policy(mode, nodes);
 171 }
 172
 173 /* Generate a custom zonelist for the BIND policy. */
 174 static struct zonelist *bind_zonelist(unsigned long *nodes)
 175 {
 176         struct zonelist *zl;
 177         int num, max, nd;
 178
 179         max = 1 + MAX_NR_ZONES * bitmap_weight(nodes, MAX_NUMNODES);
 180         zl = kmalloc(sizeof(void *) * max, GFP_KERNEL);
 181         if (!zl)
 182                 return NULL;
 183         num = 0;
 184         for (nd = find_first_bit(nodes, MAX_NUMNODES);
 185              nd < MAX_NUMNODES;
 186              nd = find_next_bit(nodes, MAX_NUMNODES, 1+nd)) {
 187                 int k;
 188                 for (k = MAX_NR_ZONES-1; k >= 0; k--) {
 189                         struct zone *z = &NODE_DATA(nd)->node_zones[k];
 190                         if (!z->present_pages)
 191                                 continue;
 192                         zl->zones[num++] = z;
 193                         if (k > policy_zone)
 194                                 policy_zone = k;
 195                 }
 196         }
 197         BUG_ON(num >= max);
 198         zl->zones[num] = NULL;
 199         return zl;
 200 }
 201
 202 /* Create a new policy */
 203 static struct mempolicy *mpol_new(int mode, unsigned long *nodes)
 204 {
 205         struct mempolicy *policy;
 206
 207         PDprintk("setting mode %d nodes[0] %lx\n", mode, nodes[0]);
 208         if (mode == MPOL_DEFAULT)
 209                 return NULL;
 210         policy = kmem_cache_alloc(policy_cache, GFP_KERNEL);
 211         if (!policy)
 212                 return ERR_PTR(-ENOMEM);
 213         atomic_set(&policy->refcnt, 1);
 214         switch (mode) {
 215         case MPOL_INTERLEAVE:
 216                 bitmap_copy(policy->v.nodes, nodes, MAX_NUMNODES);
 217                 break;
 218         case MPOL_PREFERRED:
 219                 policy->v.preferred_node = find_first_bit(nodes, MAX_NUMNODES);
 220                 if (policy->v.preferred_node >= MAX_NUMNODES)
 221                         policy->v.preferred_node = -1;
 222                 break;
 223         case MPOL_BIND:
 224                 policy->v.zonelist = bind_zonelist(nodes);
 225                 if (policy->v.zonelist == NULL) {
 226                         kmem_cache_free(policy_cache, policy);
 227                         return ERR_PTR(-ENOMEM);
 228                 }
 229                 break;
 230         }
 231         policy->policy = mode;
 232         return policy;
 233 }
 234
 235 /* Ensure all existing pages follow the policy. */
 236 static int
 237 verify_pages(unsigned long addr, unsigned long end, unsigned long *nodes)
 238 {
 239         while (addr < end) {
 240                 struct page *p;
 241                 pte_t *pte;
 242                 pmd_t *pmd;
 243                 pgd_t *pgd = pgd_offset_k(addr);
 244                 if (pgd_none(*pgd)) {
 245                         addr = (addr + PGDIR_SIZE) & PGDIR_MASK;
 246                         continue;
 247                 }
 248                 pmd = pmd_offset(pgd, addr);
 249                 if (pmd_none(*pmd)) {
 250                         addr = (addr + PMD_SIZE) & PMD_MASK;
 251                         continue;
 252                 }
 253                 p = NULL;
 254                 pte = pte_offset_map(pmd, addr);
 255                 if (pte_present(*pte))
 256                         p = pte_page(*pte);
 257                 pte_unmap(pte);
 258                 if (p) {
 259                         unsigned nid = page_to_nid(p);
 260                         if (!test_bit(nid, nodes))
 261                                 return -EIO;
 262                 }
 263                 addr += PAGE_SIZE;
 264         }
 265         return 0;
 266 }
 267
 268 /* Step 1: check the range */
 269 static struct vm_area_struct *
 270 check_range(struct mm_struct *mm, unsigned long start, unsigned long end,
 271             unsigned long *nodes, unsigned long flags)
 272 {
 273         int err;
 274         struct vm_area_struct *first, *vma, *prev;
 275
 276         first = find_vma(mm, start);
 277         if (!first)
 278                 return ERR_PTR(-EFAULT);
 279         prev = NULL;
 280         for (vma = first; vma && vma->vm_start < end; vma = vma->vm_next) {
 281                 if (!vma->vm_next && vma->vm_end < end)
 282                         return ERR_PTR(-EFAULT);
 283                 if (prev && prev->vm_end < vma->vm_start)
 284                         return ERR_PTR(-EFAULT);
 285                 if ((flags & MPOL_MF_STRICT) && !is_vm_hugetlb_page(vma)) {
 286                         err = verify_pages(vma->vm_start, vma->vm_end, nodes);
 287                         if (err) {
 288                                 first = ERR_PTR(err);
 289                                 break;
 290                         }
 291                 }
 292                 prev = vma;
 293         }
 294         return first;
 295 }
 296
 297 /* Apply policy to a single VMA */
 298 static int policy_vma(struct vm_area_struct *vma, struct mempolicy *new)
 299 {
 300         int err = 0;
 301         struct mempolicy *old = vma->vm_policy;
 302
 303         PDprintk("vma %lx-%lx/%lx vm_ops %p vm_file %p set_policy %p\n",
 304                  vma->vm_start, vma->vm_end, vma->vm_pgoff,
 305                  vma->vm_ops, vma->vm_file,
 306                  vma->vm_ops ? vma->vm_ops->set_policy : NULL);
 307
 308         if (vma->vm_ops && vma->vm_ops->set_policy)
 309                 err = vma->vm_ops->set_policy(vma, new);
 310         if (!err) {
 311                 mpol_get(new);
 312                 vma->vm_policy = new;
 313                 mpol_free(old);
 314         }
 315         return err;
 316 }
 317
 318 /* Step 2: apply policy to a range and do splits. */
 319 static int mbind_range(struct vm_area_struct *vma, unsigned long start,
 320                        unsigned long end, struct mempolicy *new)
 321 {
 322         struct vm_area_struct *next;
 323         int err;
 324
 325         err = 0;
 326         for (; vma && vma->vm_start < end; vma = next) {
 327                 next = vma->vm_next;
 328                 if (vma->vm_start < start)
 329                         err = split_vma(vma->vm_mm, vma, start, 1);
 330                 if (!err && vma->vm_end > end)
 331                         err = split_vma(vma->vm_mm, vma, end, 0);
 332                 if (!err)
 333                         err = policy_vma(vma, new);
 334                 if (err)
 335                         break;
 336         }
 337         return err;
 338 }
 339
 340 /* Change policy for a memory range */
 341 asmlinkage long sys_mbind(unsigned long start, unsigned long len,
 342                           unsigned long mode,
 343                           unsigned long __user *nmask, unsigned long maxnode,
 344                           unsigned flags)
 345 {
 346         struct vm_area_struct *vma;
 347         struct mm_struct *mm = current->mm;
 348         struct mempolicy *new;
 349         unsigned long end;
 350         DECLARE_BITMAP(nodes, MAX_NUMNODES);
 351         int err;
 352
 353         if ((flags & ~(unsigned long)(MPOL_MF_STRICT)) || mode > MPOL_MAX)
 354                 return -EINVAL;
 355         if (start & ~PAGE_MASK)
 356                 return -EINVAL;
 357         if (mode == MPOL_DEFAULT)
 358                 flags &= ~MPOL_MF_STRICT;
 359         len = (len + PAGE_SIZE - 1) & PAGE_MASK;
 360         end = start + len;
 361         if (end < start)
 362                 return -EINVAL;
 363         if (end == start)
 364                 return 0;
 365
 366         err = get_nodes(nodes, nmask, maxnode, mode);
 367         if (err)
 368                 return err;
 369
 370         new = mpol_new(mode, nodes);
 371         if (IS_ERR(new))
 372                 return PTR_ERR(new);
 373
 374         PDprintk("mbind %lx-%lx mode:%ld nodes:%lx\n",start,start+len,
 375                         mode,nodes[0]);
 376
 377         down_write(&mm->mmap_sem);
 378         vma = check_range(mm, start, end, nodes, flags);
 379         err = PTR_ERR(vma);
 380         if (!IS_ERR(vma))
 381                 err = mbind_range(vma, start, end, new);
 382         up_write(&mm->mmap_sem);
 383         mpol_free(new);
 384         return err;
 385 }
 386
 387 /* Set the process memory policy */
 388 asmlinkage long sys_set_mempolicy(int mode, unsigned long __user *nmask,
 389                                    unsigned long maxnode)
 390 {
 391         int err;
 392         struct mempolicy *new;
 393         DECLARE_BITMAP(nodes, MAX_NUMNODES);
 394
 395         if (mode > MPOL_MAX)
 396                 return -EINVAL;
 397         err = get_nodes(nodes, nmask, maxnode, mode);
 398         if (err)
 399                 return err;
 400         new = mpol_new(mode, nodes);
 401         if (IS_ERR(new))
 402                 return PTR_ERR(new);
 403         mpol_free(current->mempolicy);
 404         current->mempolicy = new;
 405         if (new && new->policy == MPOL_INTERLEAVE)
 406                 current->il_next = find_first_bit(new->v.nodes, MAX_NUMNODES);
 407         return 0;
 408 }
 409
 410 /* Fill a zone bitmap for a policy */
 411 static void get_zonemask(struct mempolicy *p, unsigned long *nodes)
 412 {
 413         int i;
 414
 415         bitmap_zero(nodes, MAX_NUMNODES);
 416         switch (p->policy) {
 417         case MPOL_BIND:
 418                 for (i = 0; p->v.zonelist->zones[i]; i++)
 419                         __set_bit(p->v.zonelist->zones[i]->zone_pgdat->node_id, nodes);
 420                 break;
 421         case MPOL_DEFAULT:
 422                 break;
 423         case MPOL_INTERLEAVE:
 424                 bitmap_copy(nodes, p->v.nodes, MAX_NUMNODES);
 425                 break;
 426         case MPOL_PREFERRED:
 427                 /* or use current node instead of online map? */
 428                 if (p->v.preferred_node < 0)
 429                         bitmap_copy(nodes, nodes_addr(node_online_map), MAX_NUMNODES);
 430                 else
 431                         __set_bit(p->v.preferred_node, nodes);
 432                 break;
 433         default:
 434                 BUG();
 435         }
 436 }
 437
 438 static int lookup_node(struct mm_struct *mm, unsigned long addr)
 439 {
 440         struct page *p;
 441         int err;
 442
 443         err = get_user_pages(current, mm, addr & PAGE_MASK, 1, 0, 0, &p, NULL);
 444         if (err >= 0) {
 445                 err = page_to_nid(p);
 446                 put_page(p);
 447         }
 448         return err;
 449 }
 450
 451 /* Copy a kernel node mask to user space */
 452 static int copy_nodes_to_user(unsigned long __user *mask, unsigned long maxnode,
 453                               void *nodes, unsigned nbytes)
 454 {
 455         unsigned long copy = ALIGN(maxnode-1, 64) / 8;
 456
 457         if (copy > nbytes) {
 458                 if (copy > PAGE_SIZE)
 459                         return -EINVAL;
 460                 if (clear_user((char __user *)mask + nbytes, copy - nbytes))
 461                         return -EFAULT;
 462                 copy = nbytes;
 463         }
 464         return copy_to_user(mask, nodes, copy) ? -EFAULT : 0;
 465 }
 466
 467 /* Retrieve NUMA policy */
 468 asmlinkage long sys_get_mempolicy(int __user *policy,
 469                                   unsigned long __user *nmask,
 470                                   unsigned long maxnode,
 471                                   unsigned long addr, unsigned long flags)
 472 {
 473         int err, pval;
 474         struct mm_struct *mm = current->mm;
 475         struct vm_area_struct *vma = NULL;
 476         struct mempolicy *pol = current->mempolicy;
 477
 478         if (flags & ~(unsigned long)(MPOL_F_NODE|MPOL_F_ADDR))
 479                 return -EINVAL;
 480         if (nmask != NULL && maxnode < numnodes)
 481                 return -EINVAL;
 482         if (flags & MPOL_F_ADDR) {
 483                 down_read(&mm->mmap_sem);
 484                 vma = find_vma_intersection(mm, addr, addr+1);
 485                 if (!vma) {
 486                         up_read(&mm->mmap_sem);
 487                         return -EFAULT;
 488                 }
 489                 if (vma->vm_ops && vma->vm_ops->get_policy)
 490                         pol = vma->vm_ops->get_policy(vma, addr);
 491                 else
 492                         pol = vma->vm_policy;
 493         } else if (addr)
 494                 return -EINVAL;
 495
 496         if (!pol)
 497                 pol = &default_policy;
 498
 499         if (flags & MPOL_F_NODE) {
 500                 if (flags & MPOL_F_ADDR) {
 501                         err = lookup_node(mm, addr);
 502                         if (err < 0)
 503                                 goto out;
 504                         pval = err;
 505                 } else if (pol == current->mempolicy &&
 506                                 pol->policy == MPOL_INTERLEAVE) {
 507                         pval = current->il_next;
 508                 } else {
 509                         err = -EINVAL;
 510                         goto out;
 511                 }
 512         } else
 513                 pval = pol->policy;
 514
 515         err = -EFAULT;
 516         if (policy && put_user(pval, policy))
 517                 goto out;
 518
 519         err = 0;
 520         if (nmask) {
 521                 DECLARE_BITMAP(nodes, MAX_NUMNODES);
 522                 get_zonemask(pol, nodes);
 523                 err = copy_nodes_to_user(nmask, maxnode, nodes, sizeof(nodes));
 524         }
 525
 526  out:
 527         if (vma)
 528                 up_read(&current->mm->mmap_sem);
 529         return err;
 530 }
 531
 532 #ifdef CONFIG_COMPAT
 533
 534 asmlinkage long compat_sys_get_mempolicy(int __user *policy,
 535                                      compat_ulong_t __user *nmask,
 536                                      compat_ulong_t maxnode,
 537                                      compat_ulong_t addr, compat_ulong_t flags)
 538 {
 539         long err;
 540         unsigned long __user *nm = NULL;
 541         unsigned long nr_bits, alloc_size;
 542         DECLARE_BITMAP(bm, MAX_NUMNODES);
 543
 544         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
 545         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
 546
 547         if (nmask)
 548                 nm = compat_alloc_user_space(alloc_size);
 549
 550         err = sys_get_mempolicy(policy, nm, nr_bits+1, addr, flags);
 551
 552         if (!err && nmask) {
 553                 err = copy_from_user(bm, nm, alloc_size);
 554                 /* ensure entire bitmap is zeroed */
 555                 err |= clear_user(nmask, ALIGN(maxnode-1, 8) / 8);
 556                 err |= compat_put_bitmap(nmask, bm, nr_bits);
 557         }
 558
 559         return err;
 560 }
 561
 562 asmlinkage long compat_sys_set_mempolicy(int mode, compat_ulong_t __user *nmask,
 563                                      compat_ulong_t maxnode)
 564 {
 565         long err = 0;
 566         unsigned long __user *nm = NULL;
 567         unsigned long nr_bits, alloc_size;
 568         DECLARE_BITMAP(bm, MAX_NUMNODES);
 569
 570         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
 571         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
 572
 573         if (nmask) {
 574                 err = compat_get_bitmap(bm, nmask, nr_bits);
 575                 nm = compat_alloc_user_space(alloc_size);
 576                 err |= copy_to_user(nm, bm, alloc_size);
 577         }
 578
 579         if (err)
 580                 return -EFAULT;
 581
 582         return sys_set_mempolicy(mode, nm, nr_bits+1);
 583 }
 584
 585 asmlinkage long compat_sys_mbind(compat_ulong_t start, compat_ulong_t len,
 586                              compat_ulong_t mode, compat_ulong_t __user *nmask,
 587                              compat_ulong_t maxnode, compat_ulong_t flags)
 588 {
 589         long err = 0;
 590         unsigned long __user *nm = NULL;
 591         unsigned long nr_bits, alloc_size;
 592         DECLARE_BITMAP(bm, MAX_NUMNODES);
 593
 594         nr_bits = min_t(unsigned long, maxnode-1, MAX_NUMNODES);
 595         alloc_size = ALIGN(nr_bits, BITS_PER_LONG) / 8;
 596
 597         if (nmask) {
 598                 err = compat_get_bitmap(bm, nmask, nr_bits);
 599                 nm = compat_alloc_user_space(alloc_size);
 600                 err |= copy_to_user(nm, bm, alloc_size);
 601         }
 602
 603         if (err)
 604                 return -EFAULT;
 605
 606         return sys_mbind(start, len, mode, nm, nr_bits+1, flags);
 607 }
 608
 609 #endif
 610
 611 /* Return effective policy for a VMA */
 612 static struct mempolicy *
 613 get_vma_policy(struct vm_area_struct *vma, unsigned long addr)
 614 {
 615         struct mempolicy *pol = current->mempolicy;
 616
 617         if (vma) {
 618                 if (vma->vm_ops && vma->vm_ops->get_policy)
 619                         pol = vma->vm_ops->get_policy(vma, addr);
 620                 else if (vma->vm_policy &&
 621                                 vma->vm_policy->policy != MPOL_DEFAULT)
 622                         pol = vma->vm_policy;
 623         }
 624         if (!pol)
 625                 pol = &default_policy;
 626         return pol;
 627 }
 628
 629 /* Return a zonelist representing a mempolicy */
 630 static struct zonelist *zonelist_policy(unsigned gfp, struct mempolicy *policy)
 631 {
 632         int nd;
 633
 634         switch (policy->policy) {
 635         case MPOL_PREFERRED:
 636                 nd = policy->v.preferred_node;
 637                 if (nd < 0)
 638                         nd = numa_node_id();
 639                 break;
 640         case MPOL_BIND:
 641                 /* Lower zones don't get a policy applied */
 642                 if (gfp >= policy_zone)
 643                         return policy->v.zonelist;
 644                 /*FALL THROUGH*/
 645         case MPOL_INTERLEAVE: /* should not happen */
 646         case MPOL_DEFAULT:
 647                 nd = numa_node_id();
 648                 break;
 649         default:
 650                 nd = 0;
 651                 BUG();
 652         }
 653         return NODE_DATA(nd)->node_zonelists + (gfp & GFP_ZONEMASK);
 654 }
 655
 656 /* Do dynamic interleaving for a process */
 657 static unsigned interleave_nodes(struct mempolicy *policy)
 658 {
 659         unsigned nid, next;
 660         struct task_struct *me = current;
 661
 662         nid = me->il_next;
 663         BUG_ON(nid >= MAX_NUMNODES);
 664         next = find_next_bit(policy->v.nodes, MAX_NUMNODES, 1+nid);
 665         if (next >= MAX_NUMNODES)
 666                 next = find_first_bit(policy->v.nodes, MAX_NUMNODES);
 667         me->il_next = next;
 668         return nid;
 669 }
 670
 671 /* Do static interleaving for a VMA with known offset. */
 672 static unsigned offset_il_node(struct mempolicy *pol,
 673                 struct vm_area_struct *vma, unsigned long off)
 674 {
 675         unsigned nnodes = bitmap_weight(pol->v.nodes, MAX_NUMNODES);
 676         unsigned target = (unsigned)off % nnodes;
 677         int c;
 678         int nid = -1;
 679
 680         c = 0;
 681         do {
 682                 nid = find_next_bit(pol->v.nodes, MAX_NUMNODES, nid+1);
 683                 c++;
 684         } while (c <= target);
 685         BUG_ON(nid >= MAX_NUMNODES);
 686         BUG_ON(!test_bit(nid, pol->v.nodes));
 687         return nid;
 688 }
 689
 690 /* Allocate a page in interleaved policy.
 691    Own path because it needs to do special accounting. */
 692 static struct page *alloc_page_interleave(unsigned gfp, unsigned order, unsigned nid)
 693 {
 694         struct zonelist *zl;
 695         struct page *page;
 696
 697         BUG_ON(!node_online(nid));
 698         zl = NODE_DATA(nid)->node_zonelists + (gfp & GFP_ZONEMASK);
 699         page = __alloc_pages(gfp, order, zl);
 700         if (page && page_zone(page) == zl->zones[0]) {
 701                 zl->zones[0]->pageset[get_cpu()].interleave_hit++;
 702                 put_cpu();
 703         }
 704         return page;
 705 }
 706
 707 /**
 708  *      alloc_page_vma  - Allocate a page for a VMA.
 709  *
 710  *      @gfp:
 711  *      %GFP_USER    user allocation.
 712  *      %GFP_KERNEL  kernel allocations,
 713  *      %GFP_HIGHMEM highmem/user allocations,
 714  *      %GFP_FS      allocation should not call back into a file system.
 715  *      %GFP_ATOMIC  don't sleep.
 716  *
 717  *      @vma:  Pointer to VMA or NULL if not available.
 718  *      @addr: Virtual Address of the allocation. Must be inside the VMA.
 719  *
 720  *      This function allocates a page from the kernel page pool and applies
 721  *      a NUMA policy associated with the VMA or the current process.
 722  *      When VMA is not NULL caller must hold down_read on the mmap_sem of the
 723  *      mm_struct of the VMA to prevent it from going away. Should be used for
 724  *      all allocations for pages that will be mapped into
 725  *      user space. Returns NULL when no page can be allocated.
 726  *
 727  *      Should be called with the mm_sem of the vma hold.
 728  */
 729 struct page *
 730 alloc_page_vma(unsigned gfp, struct vm_area_struct *vma, unsigned long addr)
 731 {
 732         struct mempolicy *pol = get_vma_policy(vma, addr);
 733
 734         if (unlikely(pol->policy == MPOL_INTERLEAVE)) {
 735                 unsigned nid;
 736                 if (vma) {
 737                         unsigned long off;
 738                         BUG_ON(addr >= vma->vm_end);
 739                         BUG_ON(addr < vma->vm_start);
 740                         off = vma->vm_pgoff;
 741                         off += (addr - vma->vm_start) >> PAGE_SHIFT;
 742                         nid = offset_il_node(pol, vma, off);
 743                 } else {
 744                         /* fall back to process interleaving */
 745                         nid = interleave_nodes(pol);
 746                 }
 747                 return alloc_page_interleave(gfp, 0, nid);
 748         }
 749         return __alloc_pages(gfp, 0, zonelist_policy(gfp, pol));
 750 }
 751
 752 /**
 753  *      alloc_pages_current - Allocate pages.
 754  *
 755  *      @gfp:
 756  *              %GFP_USER   user allocation,
 757  *              %GFP_KERNEL kernel allocation,
 758  *              %GFP_HIGHMEM highmem allocation,
 759  *              %GFP_FS     don't call back into a file system.
 760  *              %GFP_ATOMIC don't sleep.
 761  *      @order: Power of two of allocation size in pages. 0 is a single page.
 762  *
 763  *      Allocate a page from the kernel page pool.  When not in
 764  *      interrupt context and apply the current process NUMA policy.
 765  *      Returns NULL when no page can be allocated.
 766  */
 767 struct page *alloc_pages_current(unsigned gfp, unsigned order)
 768 {
 769         struct mempolicy *pol = current->mempolicy;
 770
 771         if (!pol || in_interrupt())
 772                 pol = &default_policy;
 773         if (pol->policy == MPOL_INTERLEAVE)
 774                 return alloc_page_interleave(gfp, order, interleave_nodes(pol));
 775         return __alloc_pages(gfp, order, zonelist_policy(gfp, pol));
 776 }
 777 EXPORT_SYMBOL(alloc_pages_current);
 778
 779 /* Slow path of a mempolicy copy */
 780 struct mempolicy *__mpol_copy(struct mempolicy *old)
 781 {
 782         struct mempolicy *new = kmem_cache_alloc(policy_cache, GFP_KERNEL);
 783
 784         if (!new)
 785                 return ERR_PTR(-ENOMEM);
 786         *new = *old;
 787         atomic_set(&new->refcnt, 1);
 788         if (new->policy == MPOL_BIND) {
 789                 int sz = ksize(old->v.zonelist);
 790                 new->v.zonelist = kmalloc(sz, SLAB_KERNEL);
 791                 if (!new->v.zonelist) {
 792                         kmem_cache_free(policy_cache, new);
 793                         return ERR_PTR(-ENOMEM);
 794                 }
 795                 memcpy(new->v.zonelist, old->v.zonelist, sz);
 796         }
 797         return new;
 798 }
 799
 800 /* Slow path of a mempolicy comparison */
 801 int __mpol_equal(struct mempolicy *a, struct mempolicy *b)
 802 {
 803         if (!a || !b)
 804                 return 0;
 805         if (a->policy != b->policy)
 806                 return 0;
 807         switch (a->policy) {
 808         case MPOL_DEFAULT:
 809                 return 1;
 810         case MPOL_INTERLEAVE:
 811                 return bitmap_equal(a->v.nodes, b->v.nodes, MAX_NUMNODES);
 812         case MPOL_PREFERRED:
 813                 return a->v.preferred_node == b->v.preferred_node;
 814         case MPOL_BIND: {
 815                 int i;
 816                 for (i = 0; a->v.zonelist->zones[i]; i++)
 817                         if (a->v.zonelist->zones[i] != b->v.zonelist->zones[i])
 818                                 return 0;
 819                 return b->v.zonelist->zones[i] == NULL;
 820         }
 821         default:
 822                 BUG();
 823                 return 0;
 824         }
 825 }
 826
 827 /* Slow path of a mpol destructor. */
 828 void __mpol_free(struct mempolicy *p)
 829 {
 830         if (!atomic_dec_and_test(&p->refcnt))
 831                 return;
 832         if (p->policy == MPOL_BIND)
 833                 kfree(p->v.zonelist);
 834         p->policy = MPOL_DEFAULT;
 835         kmem_cache_free(policy_cache, p);
 836 }
 837
 838 /*
 839  * Hugetlb policy. Same as above, just works with node numbers instead of
 840  * zonelists.
 841  */
 842
 843 /* Find first node suitable for an allocation */
 844 int mpol_first_node(struct vm_area_struct *vma, unsigned long addr)
 845 {
 846         struct mempolicy *pol = get_vma_policy(vma, addr);
 847
 848         switch (pol->policy) {
 849         case MPOL_DEFAULT:
 850                 return numa_node_id();
 851         case MPOL_BIND:
 852                 return pol->v.zonelist->zones[0]->zone_pgdat->node_id;
 853         case MPOL_INTERLEAVE:
 854                 return interleave_nodes(pol);
 855         case MPOL_PREFERRED:
 856                 return pol->v.preferred_node >= 0 ?
 857                                 pol->v.preferred_node : numa_node_id();
 858         }
 859         BUG();
 860         return 0;
 861 }
 862
 863 /* Find secondary valid nodes for an allocation */
 864 int mpol_node_valid(int nid, struct vm_area_struct *vma, unsigned long addr)
 865 {
 866         struct mempolicy *pol = get_vma_policy(vma, addr);
 867
 868         switch (pol->policy) {
 869         case MPOL_PREFERRED:
 870         case MPOL_DEFAULT:
 871         case MPOL_INTERLEAVE:
 872                 return 1;
 873         case MPOL_BIND: {
 874                 struct zone **z;
 875                 for (z = pol->v.zonelist->zones; *z; z++)
 876                         if ((*z)->zone_pgdat->node_id == nid)
 877                                 return 1;
 878                 return 0;
 879         }
 880         default:
 881                 BUG();
 882                 return 0;
 883         }
 884 }
 885
 886 /*
 887  * Shared memory backing store policy support.
 888  *
 889  * Remember policies even when nobody has shared memory mapped.
 890  * The policies are kept in Red-Black tree linked from the inode.
 891  * They are protected by the sp->lock spinlock, which should be held
 892  * for any accesses to the tree.
 893  */
 894
 895 /* lookup first element intersecting start-end */
 896 /* Caller holds sp->lock */
 897 static struct sp_node *
 898 sp_lookup(struct shared_policy *sp, unsigned long start, unsigned long end)
 899 {
 900         struct rb_node *n = sp->root.rb_node;
 901
 902         while (n) {
 903                 struct sp_node *p = rb_entry(n, struct sp_node, nd);
 904
 905                 if (start >= p->end)
 906                         n = n->rb_right;
 907                 else if (end <= p->start)
 908                         n = n->rb_left;
 909                 else
 910                         break;
 911         }
 912         if (!n)
 913                 return NULL;
 914         for (;;) {
 915                 struct sp_node *w = NULL;
 916                 struct rb_node *prev = rb_prev(n);
 917                 if (!prev)
 918                         break;
 919                 w = rb_entry(prev, struct sp_node, nd);
 920                 if (w->end <= start)
 921                         break;
 922                 n = prev;
 923         }
 924         return rb_entry(n, struct sp_node, nd);
 925 }
 926
 927 /* Insert a new shared policy into the list. */
 928 /* Caller holds sp->lock */
 929 static void sp_insert(struct shared_policy *sp, struct sp_node *new)
 930 {
 931         struct rb_node **p = &sp->root.rb_node;
 932         struct rb_node *parent = NULL;
 933         struct sp_node *nd;
 934
 935         while (*p) {
 936                 parent = *p;
 937                 nd = rb_entry(parent, struct sp_node, nd);
 938                 if (new->start < nd->start)
 939                         p = &(*p)->rb_left;
 940                 else if (new->end > nd->end)
 941                         p = &(*p)->rb_right;
 942                 else
 943                         BUG();
 944         }
 945         rb_link_node(&new->nd, parent, p);
 946         rb_insert_color(&new->nd, &sp->root);
 947         PDprintk("inserting %lx-%lx: %d\n", new->start, new->end,
 948                  new->policy ? new->policy->policy : 0);
 949 }
 950
 951 /* Find shared policy intersecting idx */
 952 struct mempolicy *
 953 mpol_shared_policy_lookup(struct shared_policy *sp, unsigned long idx)
 954 {
 955         struct mempolicy *pol = NULL;
 956         struct sp_node *sn;
 957
 958         if (!sp->root.rb_node)
 959                 return NULL;
 960         spin_lock(&sp->lock);
 961         sn = sp_lookup(sp, idx, idx+1);
 962         if (sn) {
 963                 mpol_get(sn->policy);
 964                 pol = sn->policy;
 965         }
 966         spin_unlock(&sp->lock);
 967         return pol;
 968 }
 969
 970 static void sp_delete(struct shared_policy *sp, struct sp_node *n)
 971 {
 972         PDprintk("deleting %lx-l%x\n", n->start, n->end);
 973         rb_erase(&n->nd, &sp->root);
 974         mpol_free(n->policy);
 975         kmem_cache_free(sn_cache, n);
 976 }
 977
 978 struct sp_node *
 979 sp_alloc(unsigned long start, unsigned long end, struct mempolicy *pol)
 980 {
 981         struct sp_node *n = kmem_cache_alloc(sn_cache, GFP_KERNEL);
 982
 983         if (!n)
 984                 return NULL;
 985         n->start = start;
 986         n->end = end;
 987         mpol_get(pol);
 988         n->policy = pol;
 989         return n;
 990 }
 991
 992 /* Replace a policy range. */
 993 static int shared_policy_replace(struct shared_policy *sp, unsigned long start,
 994                                  unsigned long end, struct sp_node *new)
 995 {
 996         struct sp_node *n, *new2 = NULL;
 997
 998 restart:
 999         spin_lock(&sp->lock);
1000         n = sp_lookup(sp, start, end);
1001         /* Take care of old policies in the same range. */
1002         while (n && n->start < end) {
1003                 struct rb_node *next = rb_next(&n->nd);
1004                 if (n->start >= start) {
1005                         if (n->end <= end)
1006                                 sp_delete(sp, n);
1007                         else
1008                                 n->start = end;
1009                 } else {
1010                         /* Old policy spanning whole new range. */
1011                         if (n->end > end) {
1012                                 if (!new2) {
1013                                         spin_unlock(&sp->lock);
1014                                         new2 = sp_alloc(end, n->end, n->policy);
1015                                         if (!new2)
1016                                                 return -ENOMEM;
1017                                         goto restart;
1018                                 }
1019                                 n->end = end;
1020                                 sp_insert(sp, new2);
1021                                 new2 = NULL;
1022                         }
1023                         /* Old crossing beginning, but not end (easy) */
1024                         if (n->start < start && n->end > start)
1025                                 n->end = start;
1026                 }
1027                 if (!next)
1028                         break;
1029                 n = rb_entry(next, struct sp_node, nd);
1030         }
1031         if (new)
1032                 sp_insert(sp, new);
1033         spin_unlock(&sp->lock);
1034         if (new2) {
1035                 mpol_free(new2->policy);
1036                 kmem_cache_free(sn_cache, new2);
1037         }
1038         return 0;
1039 }
1040
1041 int mpol_set_shared_policy(struct shared_policy *info,
1042                         struct vm_area_struct *vma, struct mempolicy *npol)
1043 {
1044         int err;
1045         struct sp_node *new = NULL;
1046         unsigned long sz = vma_pages(vma);
1047
1048         PDprintk("set_shared_policy %lx sz %lu %d %lx\n",
1049                  vma->vm_pgoff,
1050                  sz, npol? npol->policy : -1,
1051                 npol ? npol->v.nodes[0] : -1);
1052
1053         if (npol) {
1054                 new = sp_alloc(vma->vm_pgoff, vma->vm_pgoff + sz, npol);
1055                 if (!new)
1056                         return -ENOMEM;
1057         }
1058         err = shared_policy_replace(info, vma->vm_pgoff, vma->vm_pgoff+sz, new);
1059         if (err && new)
1060                 kmem_cache_free(sn_cache, new);
1061         return err;
1062 }
1063
1064 /* Free a backing policy store on inode delete. */
1065 void mpol_free_shared_policy(struct shared_policy *p)
1066 {
1067         struct sp_node *n;
1068         struct rb_node *next;
1069
1070         if (!p->root.rb_node)
1071                 return;
1072         spin_lock(&p->lock);
1073         next = rb_first(&p->root);
1074         while (next) {
1075                 n = rb_entry(next, struct sp_node, nd);
1076                 next = rb_next(&n->nd);
1077                 rb_erase(&n->nd, &p->root);
1078                 mpol_free(n->policy);
1079                 kmem_cache_free(sn_cache, n);
1080         }
1081         spin_unlock(&p->lock);
1082 }
1083
1084 /* assumes fs == KERNEL_DS */
1085 void __init numa_policy_init(void)
1086 {
1087         policy_cache = kmem_cache_create("numa_policy",
1088                                          sizeof(struct mempolicy),
1089                                          0, SLAB_PANIC, NULL, NULL);
1090
1091         sn_cache = kmem_cache_create("shared_policy_node",
1092                                      sizeof(struct sp_node),
1093                                      0, SLAB_PANIC, NULL, NULL);
1094
1095         /* Set interleaving policy for system init. This way not all
1096            the data structures allocated at system boot end up in node zero. */
1097
1098         if (sys_set_mempolicy(MPOL_INTERLEAVE, nodes_addr(node_online_map),
1099                                                         MAX_NUMNODES) < 0)
1100                 printk("numa_policy_init: interleaving failed\n");
1101 }
1102
1103 /* Reset policy of current process to default.
1104  * Assumes fs == KERNEL_DS */
1105 void numa_default_policy(void)
1106 {
1107         sys_set_mempolicy(MPOL_DEFAULT, NULL, 0);
1108 }