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