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