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