linux/mm/mmap.c
<<
>>
Prefs
   1/*
   2 * mm/mmap.c
   3 *
   4 * Written by obz.
   5 *
   6 * Address space accounting code        <alan@lxorguk.ukuu.org.uk>
   7 */
   8
   9#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  10
  11#include <linux/kernel.h>
  12#include <linux/slab.h>
  13#include <linux/backing-dev.h>
  14#include <linux/mm.h>
  15#include <linux/vmacache.h>
  16#include <linux/shm.h>
  17#include <linux/mman.h>
  18#include <linux/pagemap.h>
  19#include <linux/swap.h>
  20#include <linux/syscalls.h>
  21#include <linux/capability.h>
  22#include <linux/init.h>
  23#include <linux/file.h>
  24#include <linux/fs.h>
  25#include <linux/personality.h>
  26#include <linux/security.h>
  27#include <linux/hugetlb.h>
  28#include <linux/shmem_fs.h>
  29#include <linux/profile.h>
  30#include <linux/export.h>
  31#include <linux/mount.h>
  32#include <linux/mempolicy.h>
  33#include <linux/rmap.h>
  34#include <linux/mmu_notifier.h>
  35#include <linux/mmdebug.h>
  36#include <linux/perf_event.h>
  37#include <linux/audit.h>
  38#include <linux/khugepaged.h>
  39#include <linux/uprobes.h>
  40#include <linux/rbtree_augmented.h>
  41#include <linux/notifier.h>
  42#include <linux/memory.h>
  43#include <linux/printk.h>
  44#include <linux/userfaultfd_k.h>
  45#include <linux/moduleparam.h>
  46#include <linux/pkeys.h>
  47#include <linux/oom.h>
  48
  49#include <linux/uaccess.h>
  50#include <asm/cacheflush.h>
  51#include <asm/tlb.h>
  52#include <asm/mmu_context.h>
  53
  54#include "internal.h"
  55
  56#ifndef arch_mmap_check
  57#define arch_mmap_check(addr, len, flags)       (0)
  58#endif
  59
  60#ifdef CONFIG_HAVE_ARCH_MMAP_RND_BITS
  61const int mmap_rnd_bits_min = CONFIG_ARCH_MMAP_RND_BITS_MIN;
  62const int mmap_rnd_bits_max = CONFIG_ARCH_MMAP_RND_BITS_MAX;
  63int mmap_rnd_bits __read_mostly = CONFIG_ARCH_MMAP_RND_BITS;
  64#endif
  65#ifdef CONFIG_HAVE_ARCH_MMAP_RND_COMPAT_BITS
  66const int mmap_rnd_compat_bits_min = CONFIG_ARCH_MMAP_RND_COMPAT_BITS_MIN;
  67const int mmap_rnd_compat_bits_max = CONFIG_ARCH_MMAP_RND_COMPAT_BITS_MAX;
  68int mmap_rnd_compat_bits __read_mostly = CONFIG_ARCH_MMAP_RND_COMPAT_BITS;
  69#endif
  70
  71static bool ignore_rlimit_data;
  72core_param(ignore_rlimit_data, ignore_rlimit_data, bool, 0644);
  73
  74static void unmap_region(struct mm_struct *mm,
  75                struct vm_area_struct *vma, struct vm_area_struct *prev,
  76                unsigned long start, unsigned long end);
  77
  78/* description of effects of mapping type and prot in current implementation.
  79 * this is due to the limited x86 page protection hardware.  The expected
  80 * behavior is in parens:
  81 *
  82 * map_type     prot
  83 *              PROT_NONE       PROT_READ       PROT_WRITE      PROT_EXEC
  84 * MAP_SHARED   r: (no) no      r: (yes) yes    r: (no) yes     r: (no) yes
  85 *              w: (no) no      w: (no) no      w: (yes) yes    w: (no) no
  86 *              x: (no) no      x: (no) yes     x: (no) yes     x: (yes) yes
  87 *
  88 * MAP_PRIVATE  r: (no) no      r: (yes) yes    r: (no) yes     r: (no) yes
  89 *              w: (no) no      w: (no) no      w: (copy) copy  w: (no) no
  90 *              x: (no) no      x: (no) yes     x: (no) yes     x: (yes) yes
  91 *
  92 * On arm64, PROT_EXEC has the following behaviour for both MAP_SHARED and
  93 * MAP_PRIVATE:
  94 *                                                              r: (no) no
  95 *                                                              w: (no) no
  96 *                                                              x: (yes) yes
  97 */
  98pgprot_t protection_map[16] __ro_after_init = {
  99        __P000, __P001, __P010, __P011, __P100, __P101, __P110, __P111,
 100        __S000, __S001, __S010, __S011, __S100, __S101, __S110, __S111
 101};
 102
 103#ifndef CONFIG_ARCH_HAS_FILTER_PGPROT
 104static inline pgprot_t arch_filter_pgprot(pgprot_t prot)
 105{
 106        return prot;
 107}
 108#endif
 109
 110pgprot_t vm_get_page_prot(unsigned long vm_flags)
 111{
 112        pgprot_t ret = __pgprot(pgprot_val(protection_map[vm_flags &
 113                                (VM_READ|VM_WRITE|VM_EXEC|VM_SHARED)]) |
 114                        pgprot_val(arch_vm_get_page_prot(vm_flags)));
 115
 116        return arch_filter_pgprot(ret);
 117}
 118EXPORT_SYMBOL(vm_get_page_prot);
 119
 120static pgprot_t vm_pgprot_modify(pgprot_t oldprot, unsigned long vm_flags)
 121{
 122        return pgprot_modify(oldprot, vm_get_page_prot(vm_flags));
 123}
 124
 125/* Update vma->vm_page_prot to reflect vma->vm_flags. */
 126void vma_set_page_prot(struct vm_area_struct *vma)
 127{
 128        unsigned long vm_flags = vma->vm_flags;
 129        pgprot_t vm_page_prot;
 130
 131        vm_page_prot = vm_pgprot_modify(vma->vm_page_prot, vm_flags);
 132        if (vma_wants_writenotify(vma, vm_page_prot)) {
 133                vm_flags &= ~VM_SHARED;
 134                vm_page_prot = vm_pgprot_modify(vm_page_prot, vm_flags);
 135        }
 136        /* remove_protection_ptes reads vma->vm_page_prot without mmap_sem */
 137        WRITE_ONCE(vma->vm_page_prot, vm_page_prot);
 138}
 139
 140/*
 141 * Requires inode->i_mapping->i_mmap_rwsem
 142 */
 143static void __remove_shared_vm_struct(struct vm_area_struct *vma,
 144                struct file *file, struct address_space *mapping)
 145{
 146        if (vma->vm_flags & VM_DENYWRITE)
 147                atomic_inc(&file_inode(file)->i_writecount);
 148        if (vma->vm_flags & VM_SHARED)
 149                mapping_unmap_writable(mapping);
 150
 151        flush_dcache_mmap_lock(mapping);
 152        vma_interval_tree_remove(vma, &mapping->i_mmap);
 153        flush_dcache_mmap_unlock(mapping);
 154}
 155
 156/*
 157 * Unlink a file-based vm structure from its interval tree, to hide
 158 * vma from rmap and vmtruncate before freeing its page tables.
 159 */
 160void unlink_file_vma(struct vm_area_struct *vma)
 161{
 162        struct file *file = vma->vm_file;
 163
 164        if (file) {
 165                struct address_space *mapping = file->f_mapping;
 166                i_mmap_lock_write(mapping);
 167                __remove_shared_vm_struct(vma, file, mapping);
 168                i_mmap_unlock_write(mapping);
 169        }
 170}
 171
 172/*
 173 * Close a vm structure and free it, returning the next.
 174 */
 175static struct vm_area_struct *remove_vma(struct vm_area_struct *vma)
 176{
 177        struct vm_area_struct *next = vma->vm_next;
 178
 179        might_sleep();
 180        if (vma->vm_ops && vma->vm_ops->close)
 181                vma->vm_ops->close(vma);
 182        if (vma->vm_file)
 183                fput(vma->vm_file);
 184        mpol_put(vma_policy(vma));
 185        vm_area_free(vma);
 186        return next;
 187}
 188
 189static int do_brk_flags(unsigned long addr, unsigned long request, unsigned long flags,
 190                struct list_head *uf);
 191SYSCALL_DEFINE1(brk, unsigned long, brk)
 192{
 193        unsigned long retval;
 194        unsigned long newbrk, oldbrk, origbrk;
 195        struct mm_struct *mm = current->mm;
 196        struct vm_area_struct *next;
 197        unsigned long min_brk;
 198        bool populate;
 199        bool downgraded = false;
 200        LIST_HEAD(uf);
 201
 202        if (down_write_killable(&mm->mmap_sem))
 203                return -EINTR;
 204
 205        origbrk = mm->brk;
 206
 207#ifdef CONFIG_COMPAT_BRK
 208        /*
 209         * CONFIG_COMPAT_BRK can still be overridden by setting
 210         * randomize_va_space to 2, which will still cause mm->start_brk
 211         * to be arbitrarily shifted
 212         */
 213        if (current->brk_randomized)
 214                min_brk = mm->start_brk;
 215        else
 216                min_brk = mm->end_data;
 217#else
 218        min_brk = mm->start_brk;
 219#endif
 220        if (brk < min_brk)
 221                goto out;
 222
 223        /*
 224         * Check against rlimit here. If this check is done later after the test
 225         * of oldbrk with newbrk then it can escape the test and let the data
 226         * segment grow beyond its set limit the in case where the limit is
 227         * not page aligned -Ram Gupta
 228         */
 229        if (check_data_rlimit(rlimit(RLIMIT_DATA), brk, mm->start_brk,
 230                              mm->end_data, mm->start_data))
 231                goto out;
 232
 233        newbrk = PAGE_ALIGN(brk);
 234        oldbrk = PAGE_ALIGN(mm->brk);
 235        if (oldbrk == newbrk) {
 236                mm->brk = brk;
 237                goto success;
 238        }
 239
 240        /*
 241         * Always allow shrinking brk.
 242         * __do_munmap() may downgrade mmap_sem to read.
 243         */
 244        if (brk <= mm->brk) {
 245                int ret;
 246
 247                /*
 248                 * mm->brk must to be protected by write mmap_sem so update it
 249                 * before downgrading mmap_sem. When __do_munmap() fails,
 250                 * mm->brk will be restored from origbrk.
 251                 */
 252                mm->brk = brk;
 253                ret = __do_munmap(mm, newbrk, oldbrk-newbrk, &uf, true);
 254                if (ret < 0) {
 255                        mm->brk = origbrk;
 256                        goto out;
 257                } else if (ret == 1) {
 258                        downgraded = true;
 259                }
 260                goto success;
 261        }
 262
 263        /* Check against existing mmap mappings. */
 264        next = find_vma(mm, oldbrk);
 265        if (next && newbrk + PAGE_SIZE > vm_start_gap(next))
 266                goto out;
 267
 268        /* Ok, looks good - let it rip. */
 269        if (do_brk_flags(oldbrk, newbrk-oldbrk, 0, &uf) < 0)
 270                goto out;
 271        mm->brk = brk;
 272
 273success:
 274        populate = newbrk > oldbrk && (mm->def_flags & VM_LOCKED) != 0;
 275        if (downgraded)
 276                up_read(&mm->mmap_sem);
 277        else
 278                up_write(&mm->mmap_sem);
 279        userfaultfd_unmap_complete(mm, &uf);
 280        if (populate)
 281                mm_populate(oldbrk, newbrk - oldbrk);
 282        return brk;
 283
 284out:
 285        retval = origbrk;
 286        up_write(&mm->mmap_sem);
 287        return retval;
 288}
 289
 290static long vma_compute_subtree_gap(struct vm_area_struct *vma)
 291{
 292        unsigned long max, prev_end, subtree_gap;
 293
 294        /*
 295         * Note: in the rare case of a VM_GROWSDOWN above a VM_GROWSUP, we
 296         * allow two stack_guard_gaps between them here, and when choosing
 297         * an unmapped area; whereas when expanding we only require one.
 298         * That's a little inconsistent, but keeps the code here simpler.
 299         */
 300        max = vm_start_gap(vma);
 301        if (vma->vm_prev) {
 302                prev_end = vm_end_gap(vma->vm_prev);
 303                if (max > prev_end)
 304                        max -= prev_end;
 305                else
 306                        max = 0;
 307        }
 308        if (vma->vm_rb.rb_left) {
 309                subtree_gap = rb_entry(vma->vm_rb.rb_left,
 310                                struct vm_area_struct, vm_rb)->rb_subtree_gap;
 311                if (subtree_gap > max)
 312                        max = subtree_gap;
 313        }
 314        if (vma->vm_rb.rb_right) {
 315                subtree_gap = rb_entry(vma->vm_rb.rb_right,
 316                                struct vm_area_struct, vm_rb)->rb_subtree_gap;
 317                if (subtree_gap > max)
 318                        max = subtree_gap;
 319        }
 320        return max;
 321}
 322
 323#ifdef CONFIG_DEBUG_VM_RB
 324static int browse_rb(struct mm_struct *mm)
 325{
 326        struct rb_root *root = &mm->mm_rb;
 327        int i = 0, j, bug = 0;
 328        struct rb_node *nd, *pn = NULL;
 329        unsigned long prev = 0, pend = 0;
 330
 331        for (nd = rb_first(root); nd; nd = rb_next(nd)) {
 332                struct vm_area_struct *vma;
 333                vma = rb_entry(nd, struct vm_area_struct, vm_rb);
 334                if (vma->vm_start < prev) {
 335                        pr_emerg("vm_start %lx < prev %lx\n",
 336                                  vma->vm_start, prev);
 337                        bug = 1;
 338                }
 339                if (vma->vm_start < pend) {
 340                        pr_emerg("vm_start %lx < pend %lx\n",
 341                                  vma->vm_start, pend);
 342                        bug = 1;
 343                }
 344                if (vma->vm_start > vma->vm_end) {
 345                        pr_emerg("vm_start %lx > vm_end %lx\n",
 346                                  vma->vm_start, vma->vm_end);
 347                        bug = 1;
 348                }
 349                spin_lock(&mm->page_table_lock);
 350                if (vma->rb_subtree_gap != vma_compute_subtree_gap(vma)) {
 351                        pr_emerg("free gap %lx, correct %lx\n",
 352                               vma->rb_subtree_gap,
 353                               vma_compute_subtree_gap(vma));
 354                        bug = 1;
 355                }
 356                spin_unlock(&mm->page_table_lock);
 357                i++;
 358                pn = nd;
 359                prev = vma->vm_start;
 360                pend = vma->vm_end;
 361        }
 362        j = 0;
 363        for (nd = pn; nd; nd = rb_prev(nd))
 364                j++;
 365        if (i != j) {
 366                pr_emerg("backwards %d, forwards %d\n", j, i);
 367                bug = 1;
 368        }
 369        return bug ? -1 : i;
 370}
 371
 372static void validate_mm_rb(struct rb_root *root, struct vm_area_struct *ignore)
 373{
 374        struct rb_node *nd;
 375
 376        for (nd = rb_first(root); nd; nd = rb_next(nd)) {
 377                struct vm_area_struct *vma;
 378                vma = rb_entry(nd, struct vm_area_struct, vm_rb);
 379                VM_BUG_ON_VMA(vma != ignore &&
 380                        vma->rb_subtree_gap != vma_compute_subtree_gap(vma),
 381                        vma);
 382        }
 383}
 384
 385static void validate_mm(struct mm_struct *mm)
 386{
 387        int bug = 0;
 388        int i = 0;
 389        unsigned long highest_address = 0;
 390        struct vm_area_struct *vma = mm->mmap;
 391
 392        while (vma) {
 393                struct anon_vma *anon_vma = vma->anon_vma;
 394                struct anon_vma_chain *avc;
 395
 396                if (anon_vma) {
 397                        anon_vma_lock_read(anon_vma);
 398                        list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
 399                                anon_vma_interval_tree_verify(avc);
 400                        anon_vma_unlock_read(anon_vma);
 401                }
 402
 403                highest_address = vm_end_gap(vma);
 404                vma = vma->vm_next;
 405                i++;
 406        }
 407        if (i != mm->map_count) {
 408                pr_emerg("map_count %d vm_next %d\n", mm->map_count, i);
 409                bug = 1;
 410        }
 411        if (highest_address != mm->highest_vm_end) {
 412                pr_emerg("mm->highest_vm_end %lx, found %lx\n",
 413                          mm->highest_vm_end, highest_address);
 414                bug = 1;
 415        }
 416        i = browse_rb(mm);
 417        if (i != mm->map_count) {
 418                if (i != -1)
 419                        pr_emerg("map_count %d rb %d\n", mm->map_count, i);
 420                bug = 1;
 421        }
 422        VM_BUG_ON_MM(bug, mm);
 423}
 424#else
 425#define validate_mm_rb(root, ignore) do { } while (0)
 426#define validate_mm(mm) do { } while (0)
 427#endif
 428
 429RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb,
 430                     unsigned long, rb_subtree_gap, vma_compute_subtree_gap)
 431
 432/*
 433 * Update augmented rbtree rb_subtree_gap values after vma->vm_start or
 434 * vma->vm_prev->vm_end values changed, without modifying the vma's position
 435 * in the rbtree.
 436 */
 437static void vma_gap_update(struct vm_area_struct *vma)
 438{
 439        /*
 440         * As it turns out, RB_DECLARE_CALLBACKS() already created a callback
 441         * function that does exacltly what we want.
 442         */
 443        vma_gap_callbacks_propagate(&vma->vm_rb, NULL);
 444}
 445
 446static inline void vma_rb_insert(struct vm_area_struct *vma,
 447                                 struct rb_root *root)
 448{
 449        /* All rb_subtree_gap values must be consistent prior to insertion */
 450        validate_mm_rb(root, NULL);
 451
 452        rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks);
 453}
 454
 455static void __vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root)
 456{
 457        /*
 458         * Note rb_erase_augmented is a fairly large inline function,
 459         * so make sure we instantiate it only once with our desired
 460         * augmented rbtree callbacks.
 461         */
 462        rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks);
 463}
 464
 465static __always_inline void vma_rb_erase_ignore(struct vm_area_struct *vma,
 466                                                struct rb_root *root,
 467                                                struct vm_area_struct *ignore)
 468{
 469        /*
 470         * All rb_subtree_gap values must be consistent prior to erase,
 471         * with the possible exception of the "next" vma being erased if
 472         * next->vm_start was reduced.
 473         */
 474        validate_mm_rb(root, ignore);
 475
 476        __vma_rb_erase(vma, root);
 477}
 478
 479static __always_inline void vma_rb_erase(struct vm_area_struct *vma,
 480                                         struct rb_root *root)
 481{
 482        /*
 483         * All rb_subtree_gap values must be consistent prior to erase,
 484         * with the possible exception of the vma being erased.
 485         */
 486        validate_mm_rb(root, vma);
 487
 488        __vma_rb_erase(vma, root);
 489}
 490
 491/*
 492 * vma has some anon_vma assigned, and is already inserted on that
 493 * anon_vma's interval trees.
 494 *
 495 * Before updating the vma's vm_start / vm_end / vm_pgoff fields, the
 496 * vma must be removed from the anon_vma's interval trees using
 497 * anon_vma_interval_tree_pre_update_vma().
 498 *
 499 * After the update, the vma will be reinserted using
 500 * anon_vma_interval_tree_post_update_vma().
 501 *
 502 * The entire update must be protected by exclusive mmap_sem and by
 503 * the root anon_vma's mutex.
 504 */
 505static inline void
 506anon_vma_interval_tree_pre_update_vma(struct vm_area_struct *vma)
 507{
 508        struct anon_vma_chain *avc;
 509
 510        list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
 511                anon_vma_interval_tree_remove(avc, &avc->anon_vma->rb_root);
 512}
 513
 514static inline void
 515anon_vma_interval_tree_post_update_vma(struct vm_area_struct *vma)
 516{
 517        struct anon_vma_chain *avc;
 518
 519        list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
 520                anon_vma_interval_tree_insert(avc, &avc->anon_vma->rb_root);
 521}
 522
 523static int find_vma_links(struct mm_struct *mm, unsigned long addr,
 524                unsigned long end, struct vm_area_struct **pprev,
 525                struct rb_node ***rb_link, struct rb_node **rb_parent)
 526{
 527        struct rb_node **__rb_link, *__rb_parent, *rb_prev;
 528
 529        __rb_link = &mm->mm_rb.rb_node;
 530        rb_prev = __rb_parent = NULL;
 531
 532        while (*__rb_link) {
 533                struct vm_area_struct *vma_tmp;
 534
 535                __rb_parent = *__rb_link;
 536                vma_tmp = rb_entry(__rb_parent, struct vm_area_struct, vm_rb);
 537
 538                if (vma_tmp->vm_end > addr) {
 539                        /* Fail if an existing vma overlaps the area */
 540                        if (vma_tmp->vm_start < end)
 541                                return -ENOMEM;
 542                        __rb_link = &__rb_parent->rb_left;
 543                } else {
 544                        rb_prev = __rb_parent;
 545                        __rb_link = &__rb_parent->rb_right;
 546                }
 547        }
 548
 549        *pprev = NULL;
 550        if (rb_prev)
 551                *pprev = rb_entry(rb_prev, struct vm_area_struct, vm_rb);
 552        *rb_link = __rb_link;
 553        *rb_parent = __rb_parent;
 554        return 0;
 555}
 556
 557static unsigned long count_vma_pages_range(struct mm_struct *mm,
 558                unsigned long addr, unsigned long end)
 559{
 560        unsigned long nr_pages = 0;
 561        struct vm_area_struct *vma;
 562
 563        /* Find first overlaping mapping */
 564        vma = find_vma_intersection(mm, addr, end);
 565        if (!vma)
 566                return 0;
 567
 568        nr_pages = (min(end, vma->vm_end) -
 569                max(addr, vma->vm_start)) >> PAGE_SHIFT;
 570
 571        /* Iterate over the rest of the overlaps */
 572        for (vma = vma->vm_next; vma; vma = vma->vm_next) {
 573                unsigned long overlap_len;
 574
 575                if (vma->vm_start > end)
 576                        break;
 577
 578                overlap_len = min(end, vma->vm_end) - vma->vm_start;
 579                nr_pages += overlap_len >> PAGE_SHIFT;
 580        }
 581
 582        return nr_pages;
 583}
 584
 585void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma,
 586                struct rb_node **rb_link, struct rb_node *rb_parent)
 587{
 588        /* Update tracking information for the gap following the new vma. */
 589        if (vma->vm_next)
 590                vma_gap_update(vma->vm_next);
 591        else
 592                mm->highest_vm_end = vm_end_gap(vma);
 593
 594        /*
 595         * vma->vm_prev wasn't known when we followed the rbtree to find the
 596         * correct insertion point for that vma. As a result, we could not
 597         * update the vma vm_rb parents rb_subtree_gap values on the way down.
 598         * So, we first insert the vma with a zero rb_subtree_gap value
 599         * (to be consistent with what we did on the way down), and then
 600         * immediately update the gap to the correct value. Finally we
 601         * rebalance the rbtree after all augmented values have been set.
 602         */
 603        rb_link_node(&vma->vm_rb, rb_parent, rb_link);
 604        vma->rb_subtree_gap = 0;
 605        vma_gap_update(vma);
 606        vma_rb_insert(vma, &mm->mm_rb);
 607}
 608
 609static void __vma_link_file(struct vm_area_struct *vma)
 610{
 611        struct file *file;
 612
 613        file = vma->vm_file;
 614        if (file) {
 615                struct address_space *mapping = file->f_mapping;
 616
 617                if (vma->vm_flags & VM_DENYWRITE)
 618                        atomic_dec(&file_inode(file)->i_writecount);
 619                if (vma->vm_flags & VM_SHARED)
 620                        atomic_inc(&mapping->i_mmap_writable);
 621
 622                flush_dcache_mmap_lock(mapping);
 623                vma_interval_tree_insert(vma, &mapping->i_mmap);
 624                flush_dcache_mmap_unlock(mapping);
 625        }
 626}
 627
 628static void
 629__vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 630        struct vm_area_struct *prev, struct rb_node **rb_link,
 631        struct rb_node *rb_parent)
 632{
 633        __vma_link_list(mm, vma, prev, rb_parent);
 634        __vma_link_rb(mm, vma, rb_link, rb_parent);
 635}
 636
 637static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 638                        struct vm_area_struct *prev, struct rb_node **rb_link,
 639                        struct rb_node *rb_parent)
 640{
 641        struct address_space *mapping = NULL;
 642
 643        if (vma->vm_file) {
 644                mapping = vma->vm_file->f_mapping;
 645                i_mmap_lock_write(mapping);
 646        }
 647
 648        __vma_link(mm, vma, prev, rb_link, rb_parent);
 649        __vma_link_file(vma);
 650
 651        if (mapping)
 652                i_mmap_unlock_write(mapping);
 653
 654        mm->map_count++;
 655        validate_mm(mm);
 656}
 657
 658/*
 659 * Helper for vma_adjust() in the split_vma insert case: insert a vma into the
 660 * mm's list and rbtree.  It has already been inserted into the interval tree.
 661 */
 662static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 663{
 664        struct vm_area_struct *prev;
 665        struct rb_node **rb_link, *rb_parent;
 666
 667        if (find_vma_links(mm, vma->vm_start, vma->vm_end,
 668                           &prev, &rb_link, &rb_parent))
 669                BUG();
 670        __vma_link(mm, vma, prev, rb_link, rb_parent);
 671        mm->map_count++;
 672}
 673
 674static __always_inline void __vma_unlink_common(struct mm_struct *mm,
 675                                                struct vm_area_struct *vma,
 676                                                struct vm_area_struct *prev,
 677                                                bool has_prev,
 678                                                struct vm_area_struct *ignore)
 679{
 680        struct vm_area_struct *next;
 681
 682        vma_rb_erase_ignore(vma, &mm->mm_rb, ignore);
 683        next = vma->vm_next;
 684        if (has_prev)
 685                prev->vm_next = next;
 686        else {
 687                prev = vma->vm_prev;
 688                if (prev)
 689                        prev->vm_next = next;
 690                else
 691                        mm->mmap = next;
 692        }
 693        if (next)
 694                next->vm_prev = prev;
 695
 696        /* Kill the cache */
 697        vmacache_invalidate(mm);
 698}
 699
 700static inline void __vma_unlink_prev(struct mm_struct *mm,
 701                                     struct vm_area_struct *vma,
 702                                     struct vm_area_struct *prev)
 703{
 704        __vma_unlink_common(mm, vma, prev, true, vma);
 705}
 706
 707/*
 708 * We cannot adjust vm_start, vm_end, vm_pgoff fields of a vma that
 709 * is already present in an i_mmap tree without adjusting the tree.
 710 * The following helper function should be used when such adjustments
 711 * are necessary.  The "insert" vma (if any) is to be inserted
 712 * before we drop the necessary locks.
 713 */
 714int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
 715        unsigned long end, pgoff_t pgoff, struct vm_area_struct *insert,
 716        struct vm_area_struct *expand)
 717{
 718        struct mm_struct *mm = vma->vm_mm;
 719        struct vm_area_struct *next = vma->vm_next, *orig_vma = vma;
 720        struct address_space *mapping = NULL;
 721        struct rb_root_cached *root = NULL;
 722        struct anon_vma *anon_vma = NULL;
 723        struct file *file = vma->vm_file;
 724        bool start_changed = false, end_changed = false;
 725        long adjust_next = 0;
 726        int remove_next = 0;
 727
 728        if (next && !insert) {
 729                struct vm_area_struct *exporter = NULL, *importer = NULL;
 730
 731                if (end >= next->vm_end) {
 732                        /*
 733                         * vma expands, overlapping all the next, and
 734                         * perhaps the one after too (mprotect case 6).
 735                         * The only other cases that gets here are
 736                         * case 1, case 7 and case 8.
 737                         */
 738                        if (next == expand) {
 739                                /*
 740                                 * The only case where we don't expand "vma"
 741                                 * and we expand "next" instead is case 8.
 742                                 */
 743                                VM_WARN_ON(end != next->vm_end);
 744                                /*
 745                                 * remove_next == 3 means we're
 746                                 * removing "vma" and that to do so we
 747                                 * swapped "vma" and "next".
 748                                 */
 749                                remove_next = 3;
 750                                VM_WARN_ON(file != next->vm_file);
 751                                swap(vma, next);
 752                        } else {
 753                                VM_WARN_ON(expand != vma);
 754                                /*
 755                                 * case 1, 6, 7, remove_next == 2 is case 6,
 756                                 * remove_next == 1 is case 1 or 7.
 757                                 */
 758                                remove_next = 1 + (end > next->vm_end);
 759                                VM_WARN_ON(remove_next == 2 &&
 760                                           end != next->vm_next->vm_end);
 761                                VM_WARN_ON(remove_next == 1 &&
 762                                           end != next->vm_end);
 763                                /* trim end to next, for case 6 first pass */
 764                                end = next->vm_end;
 765                        }
 766
 767                        exporter = next;
 768                        importer = vma;
 769
 770                        /*
 771                         * If next doesn't have anon_vma, import from vma after
 772                         * next, if the vma overlaps with it.
 773                         */
 774                        if (remove_next == 2 && !next->anon_vma)
 775                                exporter = next->vm_next;
 776
 777                } else if (end > next->vm_start) {
 778                        /*
 779                         * vma expands, overlapping part of the next:
 780                         * mprotect case 5 shifting the boundary up.
 781                         */
 782                        adjust_next = (end - next->vm_start) >> PAGE_SHIFT;
 783                        exporter = next;
 784                        importer = vma;
 785                        VM_WARN_ON(expand != importer);
 786                } else if (end < vma->vm_end) {
 787                        /*
 788                         * vma shrinks, and !insert tells it's not
 789                         * split_vma inserting another: so it must be
 790                         * mprotect case 4 shifting the boundary down.
 791                         */
 792                        adjust_next = -((vma->vm_end - end) >> PAGE_SHIFT);
 793                        exporter = vma;
 794                        importer = next;
 795                        VM_WARN_ON(expand != importer);
 796                }
 797
 798                /*
 799                 * Easily overlooked: when mprotect shifts the boundary,
 800                 * make sure the expanding vma has anon_vma set if the
 801                 * shrinking vma had, to cover any anon pages imported.
 802                 */
 803                if (exporter && exporter->anon_vma && !importer->anon_vma) {
 804                        int error;
 805
 806                        importer->anon_vma = exporter->anon_vma;
 807                        error = anon_vma_clone(importer, exporter);
 808                        if (error)
 809                                return error;
 810                }
 811        }
 812again:
 813        vma_adjust_trans_huge(orig_vma, start, end, adjust_next);
 814
 815        if (file) {
 816                mapping = file->f_mapping;
 817                root = &mapping->i_mmap;
 818                uprobe_munmap(vma, vma->vm_start, vma->vm_end);
 819
 820                if (adjust_next)
 821                        uprobe_munmap(next, next->vm_start, next->vm_end);
 822
 823                i_mmap_lock_write(mapping);
 824                if (insert) {
 825                        /*
 826                         * Put into interval tree now, so instantiated pages
 827                         * are visible to arm/parisc __flush_dcache_page
 828                         * throughout; but we cannot insert into address
 829                         * space until vma start or end is updated.
 830                         */
 831                        __vma_link_file(insert);
 832                }
 833        }
 834
 835        anon_vma = vma->anon_vma;
 836        if (!anon_vma && adjust_next)
 837                anon_vma = next->anon_vma;
 838        if (anon_vma) {
 839                VM_WARN_ON(adjust_next && next->anon_vma &&
 840                           anon_vma != next->anon_vma);
 841                anon_vma_lock_write(anon_vma);
 842                anon_vma_interval_tree_pre_update_vma(vma);
 843                if (adjust_next)
 844                        anon_vma_interval_tree_pre_update_vma(next);
 845        }
 846
 847        if (root) {
 848                flush_dcache_mmap_lock(mapping);
 849                vma_interval_tree_remove(vma, root);
 850                if (adjust_next)
 851                        vma_interval_tree_remove(next, root);
 852        }
 853
 854        if (start != vma->vm_start) {
 855                vma->vm_start = start;
 856                start_changed = true;
 857        }
 858        if (end != vma->vm_end) {
 859                vma->vm_end = end;
 860                end_changed = true;
 861        }
 862        vma->vm_pgoff = pgoff;
 863        if (adjust_next) {
 864                next->vm_start += adjust_next << PAGE_SHIFT;
 865                next->vm_pgoff += adjust_next;
 866        }
 867
 868        if (root) {
 869                if (adjust_next)
 870                        vma_interval_tree_insert(next, root);
 871                vma_interval_tree_insert(vma, root);
 872                flush_dcache_mmap_unlock(mapping);
 873        }
 874
 875        if (remove_next) {
 876                /*
 877                 * vma_merge has merged next into vma, and needs
 878                 * us to remove next before dropping the locks.
 879                 */
 880                if (remove_next != 3)
 881                        __vma_unlink_prev(mm, next, vma);
 882                else
 883                        /*
 884                         * vma is not before next if they've been
 885                         * swapped.
 886                         *
 887                         * pre-swap() next->vm_start was reduced so
 888                         * tell validate_mm_rb to ignore pre-swap()
 889                         * "next" (which is stored in post-swap()
 890                         * "vma").
 891                         */
 892                        __vma_unlink_common(mm, next, NULL, false, vma);
 893                if (file)
 894                        __remove_shared_vm_struct(next, file, mapping);
 895        } else if (insert) {
 896                /*
 897                 * split_vma has split insert from vma, and needs
 898                 * us to insert it before dropping the locks
 899                 * (it may either follow vma or precede it).
 900                 */
 901                __insert_vm_struct(mm, insert);
 902        } else {
 903                if (start_changed)
 904                        vma_gap_update(vma);
 905                if (end_changed) {
 906                        if (!next)
 907                                mm->highest_vm_end = vm_end_gap(vma);
 908                        else if (!adjust_next)
 909                                vma_gap_update(next);
 910                }
 911        }
 912
 913        if (anon_vma) {
 914                anon_vma_interval_tree_post_update_vma(vma);
 915                if (adjust_next)
 916                        anon_vma_interval_tree_post_update_vma(next);
 917                anon_vma_unlock_write(anon_vma);
 918        }
 919        if (mapping)
 920                i_mmap_unlock_write(mapping);
 921
 922        if (root) {
 923                uprobe_mmap(vma);
 924
 925                if (adjust_next)
 926                        uprobe_mmap(next);
 927        }
 928
 929        if (remove_next) {
 930                if (file) {
 931                        uprobe_munmap(next, next->vm_start, next->vm_end);
 932                        fput(file);
 933                }
 934                if (next->anon_vma)
 935                        anon_vma_merge(vma, next);
 936                mm->map_count--;
 937                mpol_put(vma_policy(next));
 938                vm_area_free(next);
 939                /*
 940                 * In mprotect's case 6 (see comments on vma_merge),
 941                 * we must remove another next too. It would clutter
 942                 * up the code too much to do both in one go.
 943                 */
 944                if (remove_next != 3) {
 945                        /*
 946                         * If "next" was removed and vma->vm_end was
 947                         * expanded (up) over it, in turn
 948                         * "next->vm_prev->vm_end" changed and the
 949                         * "vma->vm_next" gap must be updated.
 950                         */
 951                        next = vma->vm_next;
 952                } else {
 953                        /*
 954                         * For the scope of the comment "next" and
 955                         * "vma" considered pre-swap(): if "vma" was
 956                         * removed, next->vm_start was expanded (down)
 957                         * over it and the "next" gap must be updated.
 958                         * Because of the swap() the post-swap() "vma"
 959                         * actually points to pre-swap() "next"
 960                         * (post-swap() "next" as opposed is now a
 961                         * dangling pointer).
 962                         */
 963                        next = vma;
 964                }
 965                if (remove_next == 2) {
 966                        remove_next = 1;
 967                        end = next->vm_end;
 968                        goto again;
 969                }
 970                else if (next)
 971                        vma_gap_update(next);
 972                else {
 973                        /*
 974                         * If remove_next == 2 we obviously can't
 975                         * reach this path.
 976                         *
 977                         * If remove_next == 3 we can't reach this
 978                         * path because pre-swap() next is always not
 979                         * NULL. pre-swap() "next" is not being
 980                         * removed and its next->vm_end is not altered
 981                         * (and furthermore "end" already matches
 982                         * next->vm_end in remove_next == 3).
 983                         *
 984                         * We reach this only in the remove_next == 1
 985                         * case if the "next" vma that was removed was
 986                         * the highest vma of the mm. However in such
 987                         * case next->vm_end == "end" and the extended
 988                         * "vma" has vma->vm_end == next->vm_end so
 989                         * mm->highest_vm_end doesn't need any update
 990                         * in remove_next == 1 case.
 991                         */
 992                        VM_WARN_ON(mm->highest_vm_end != vm_end_gap(vma));
 993                }
 994        }
 995        if (insert && file)
 996                uprobe_mmap(insert);
 997
 998        validate_mm(mm);
 999
1000        return 0;
1001}
1002
1003/*
1004 * If the vma has a ->close operation then the driver probably needs to release
1005 * per-vma resources, so we don't attempt to merge those.
1006 */
1007static inline int is_mergeable_vma(struct vm_area_struct *vma,
1008                                struct file *file, unsigned long vm_flags,
1009                                struct vm_userfaultfd_ctx vm_userfaultfd_ctx)
1010{
1011        /*
1012         * VM_SOFTDIRTY should not prevent from VMA merging, if we
1013         * match the flags but dirty bit -- the caller should mark
1014         * merged VMA as dirty. If dirty bit won't be excluded from
1015         * comparison, we increase pressue on the memory system forcing
1016         * the kernel to generate new VMAs when old one could be
1017         * extended instead.
1018         */
1019        if ((vma->vm_flags ^ vm_flags) & ~VM_SOFTDIRTY)
1020                return 0;
1021        if (vma->vm_file != file)
1022                return 0;
1023        if (vma->vm_ops && vma->vm_ops->close)
1024                return 0;
1025        if (!is_mergeable_vm_userfaultfd_ctx(vma, vm_userfaultfd_ctx))
1026                return 0;
1027        return 1;
1028}
1029
1030static inline int is_mergeable_anon_vma(struct anon_vma *anon_vma1,
1031                                        struct anon_vma *anon_vma2,
1032                                        struct vm_area_struct *vma)
1033{
1034        /*
1035         * The list_is_singular() test is to avoid merging VMA cloned from
1036         * parents. This can improve scalability caused by anon_vma lock.
1037         */
1038        if ((!anon_vma1 || !anon_vma2) && (!vma ||
1039                list_is_singular(&vma->anon_vma_chain)))
1040                return 1;
1041        return anon_vma1 == anon_vma2;
1042}
1043
1044/*
1045 * Return true if we can merge this (vm_flags,anon_vma,file,vm_pgoff)
1046 * in front of (at a lower virtual address and file offset than) the vma.
1047 *
1048 * We cannot merge two vmas if they have differently assigned (non-NULL)
1049 * anon_vmas, nor if same anon_vma is assigned but offsets incompatible.
1050 *
1051 * We don't check here for the merged mmap wrapping around the end of pagecache
1052 * indices (16TB on ia32) because do_mmap_pgoff() does not permit mmap's which
1053 * wrap, nor mmaps which cover the final page at index -1UL.
1054 */
1055static int
1056can_vma_merge_before(struct vm_area_struct *vma, unsigned long vm_flags,
1057                     struct anon_vma *anon_vma, struct file *file,
1058                     pgoff_t vm_pgoff,
1059                     struct vm_userfaultfd_ctx vm_userfaultfd_ctx)
1060{
1061        if (is_mergeable_vma(vma, file, vm_flags, vm_userfaultfd_ctx) &&
1062            is_mergeable_anon_vma(anon_vma, vma->anon_vma, vma)) {
1063                if (vma->vm_pgoff == vm_pgoff)
1064                        return 1;
1065        }
1066        return 0;
1067}
1068
1069/*
1070 * Return true if we can merge this (vm_flags,anon_vma,file,vm_pgoff)
1071 * beyond (at a higher virtual address and file offset than) the vma.
1072 *
1073 * We cannot merge two vmas if they have differently assigned (non-NULL)
1074 * anon_vmas, nor if same anon_vma is assigned but offsets incompatible.
1075 */
1076static int
1077can_vma_merge_after(struct vm_area_struct *vma, unsigned long vm_flags,
1078                    struct anon_vma *anon_vma, struct file *file,
1079                    pgoff_t vm_pgoff,
1080                    struct vm_userfaultfd_ctx vm_userfaultfd_ctx)
1081{
1082        if (is_mergeable_vma(vma, file, vm_flags, vm_userfaultfd_ctx) &&
1083            is_mergeable_anon_vma(anon_vma, vma->anon_vma, vma)) {
1084                pgoff_t vm_pglen;
1085                vm_pglen = vma_pages(vma);
1086                if (vma->vm_pgoff + vm_pglen == vm_pgoff)
1087                        return 1;
1088        }
1089        return 0;
1090}
1091
1092/*
1093 * Given a mapping request (addr,end,vm_flags,file,pgoff), figure out
1094 * whether that can be merged with its predecessor or its successor.
1095 * Or both (it neatly fills a hole).
1096 *
1097 * In most cases - when called for mmap, brk or mremap - [addr,end) is
1098 * certain not to be mapped by the time vma_merge is called; but when
1099 * called for mprotect, it is certain to be already mapped (either at
1100 * an offset within prev, or at the start of next), and the flags of
1101 * this area are about to be changed to vm_flags - and the no-change
1102 * case has already been eliminated.
1103 *
1104 * The following mprotect cases have to be considered, where AAAA is
1105 * the area passed down from mprotect_fixup, never extending beyond one
1106 * vma, PPPPPP is the prev vma specified, and NNNNNN the next vma after:
1107 *
1108 *     AAAA             AAAA                AAAA          AAAA
1109 *    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPNNNNXXXX
1110 *    cannot merge    might become    might become    might become
1111 *                    PPNNNNNNNNNN    PPPPPPPPPPNN    PPPPPPPPPPPP 6 or
1112 *    mmap, brk or    case 4 below    case 5 below    PPPPPPPPXXXX 7 or
1113 *    mremap move:                                    PPPPXXXXXXXX 8
1114 *        AAAA
1115 *    PPPP    NNNN    PPPPPPPPPPPP    PPPPPPPPNNNN    PPPPNNNNNNNN
1116 *    might become    case 1 below    case 2 below    case 3 below
1117 *
1118 * It is important for case 8 that the the vma NNNN overlapping the
1119 * region AAAA is never going to extended over XXXX. Instead XXXX must
1120 * be extended in region AAAA and NNNN must be removed. This way in
1121 * all cases where vma_merge succeeds, the moment vma_adjust drops the
1122 * rmap_locks, the properties of the merged vma will be already
1123 * correct for the whole merged range. Some of those properties like
1124 * vm_page_prot/vm_flags may be accessed by rmap_walks and they must
1125 * be correct for the whole merged range immediately after the
1126 * rmap_locks are released. Otherwise if XXXX would be removed and
1127 * NNNN would be extended over the XXXX range, remove_migration_ptes
1128 * or other rmap walkers (if working on addresses beyond the "end"
1129 * parameter) may establish ptes with the wrong permissions of NNNN
1130 * instead of the right permissions of XXXX.
1131 */
1132struct vm_area_struct *vma_merge(struct mm_struct *mm,
1133                        struct vm_area_struct *prev, unsigned long addr,
1134                        unsigned long end, unsigned long vm_flags,
1135                        struct anon_vma *anon_vma, struct file *file,
1136                        pgoff_t pgoff, struct mempolicy *policy,
1137                        struct vm_userfaultfd_ctx vm_userfaultfd_ctx)
1138{
1139        pgoff_t pglen = (end - addr) >> PAGE_SHIFT;
1140        struct vm_area_struct *area, *next;
1141        int err;
1142
1143        /*
1144         * We later require that vma->vm_flags == vm_flags,
1145         * so this tests vma->vm_flags & VM_SPECIAL, too.
1146         */
1147        if (vm_flags & VM_SPECIAL)
1148                return NULL;
1149
1150        if (prev)
1151                next = prev->vm_next;
1152        else
1153                next = mm->mmap;
1154        area = next;
1155        if (area && area->vm_end == end)                /* cases 6, 7, 8 */
1156                next = next->vm_next;
1157
1158        /* verify some invariant that must be enforced by the caller */
1159        VM_WARN_ON(prev && addr <= prev->vm_start);
1160        VM_WARN_ON(area && end > area->vm_end);
1161        VM_WARN_ON(addr >= end);
1162
1163        /*
1164         * Can it merge with the predecessor?
1165         */
1166        if (prev && prev->vm_end == addr &&
1167                        mpol_equal(vma_policy(prev), policy) &&
1168                        can_vma_merge_after(prev, vm_flags,
1169                                            anon_vma, file, pgoff,
1170                                            vm_userfaultfd_ctx)) {
1171                /*
1172                 * OK, it can.  Can we now merge in the successor as well?
1173                 */
1174                if (next && end == next->vm_start &&
1175                                mpol_equal(policy, vma_policy(next)) &&
1176                                can_vma_merge_before(next, vm_flags,
1177                                                     anon_vma, file,
1178                                                     pgoff+pglen,
1179                                                     vm_userfaultfd_ctx) &&
1180                                is_mergeable_anon_vma(prev->anon_vma,
1181                                                      next->anon_vma, NULL)) {
1182                                                        /* cases 1, 6 */
1183                        err = __vma_adjust(prev, prev->vm_start,
1184                                         next->vm_end, prev->vm_pgoff, NULL,
1185                                         prev);
1186                } else                                  /* cases 2, 5, 7 */
1187                        err = __vma_adjust(prev, prev->vm_start,
1188                                         end, prev->vm_pgoff, NULL, prev);
1189                if (err)
1190                        return NULL;
1191                khugepaged_enter_vma_merge(prev, vm_flags);
1192                return prev;
1193        }
1194
1195        /*
1196         * Can this new request be merged in front of next?
1197         */
1198        if (next && end == next->vm_start &&
1199                        mpol_equal(policy, vma_policy(next)) &&
1200                        can_vma_merge_before(next, vm_flags,
1201                                             anon_vma, file, pgoff+pglen,
1202                                             vm_userfaultfd_ctx)) {
1203                if (prev && addr < prev->vm_end)        /* case 4 */
1204                        err = __vma_adjust(prev, prev->vm_start,
1205                                         addr, prev->vm_pgoff, NULL, next);
1206                else {                                  /* cases 3, 8 */
1207                        err = __vma_adjust(area, addr, next->vm_end,
1208                                         next->vm_pgoff - pglen, NULL, next);
1209                        /*
1210                         * In case 3 area is already equal to next and
1211                         * this is a noop, but in case 8 "area" has
1212                         * been removed and next was expanded over it.
1213                         */
1214                        area = next;
1215                }
1216                if (err)
1217                        return NULL;
1218                khugepaged_enter_vma_merge(area, vm_flags);
1219                return area;
1220        }
1221
1222        return NULL;
1223}
1224
1225/*
1226 * Rough compatbility check to quickly see if it's even worth looking
1227 * at sharing an anon_vma.
1228 *
1229 * They need to have the same vm_file, and the flags can only differ
1230 * in things that mprotect may change.
1231 *
1232 * NOTE! The fact that we share an anon_vma doesn't _have_ to mean that
1233 * we can merge the two vma's. For example, we refuse to merge a vma if
1234 * there is a vm_ops->close() function, because that indicates that the
1235 * driver is doing some kind of reference counting. But that doesn't
1236 * really matter for the anon_vma sharing case.
1237 */
1238static int anon_vma_compatible(struct vm_area_struct *a, struct vm_area_struct *b)
1239{
1240        return a->vm_end == b->vm_start &&
1241                mpol_equal(vma_policy(a), vma_policy(b)) &&
1242                a->vm_file == b->vm_file &&
1243                !((a->vm_flags ^ b->vm_flags) & ~(VM_READ|VM_WRITE|VM_EXEC|VM_SOFTDIRTY)) &&
1244                b->vm_pgoff == a->vm_pgoff + ((b->vm_start - a->vm_start) >> PAGE_SHIFT);
1245}
1246
1247/*
1248 * Do some basic sanity checking to see if we can re-use the anon_vma
1249 * from 'old'. The 'a'/'b' vma's are in VM order - one of them will be
1250 * the same as 'old', the other will be the new one that is trying
1251 * to share the anon_vma.
1252 *
1253 * NOTE! This runs with mm_sem held for reading, so it is possible that
1254 * the anon_vma of 'old' is concurrently in the process of being set up
1255 * by another page fault trying to merge _that_. But that's ok: if it
1256 * is being set up, that automatically means that it will be a singleton
1257 * acceptable for merging, so we can do all of this optimistically. But
1258 * we do that READ_ONCE() to make sure that we never re-load the pointer.
1259 *
1260 * IOW: that the "list_is_singular()" test on the anon_vma_chain only
1261 * matters for the 'stable anon_vma' case (ie the thing we want to avoid
1262 * is to return an anon_vma that is "complex" due to having gone through
1263 * a fork).
1264 *
1265 * We also make sure that the two vma's are compatible (adjacent,
1266 * and with the same memory policies). That's all stable, even with just
1267 * a read lock on the mm_sem.
1268 */
1269static struct anon_vma *reusable_anon_vma(struct vm_area_struct *old, struct vm_area_struct *a, struct vm_area_struct *b)
1270{
1271        if (anon_vma_compatible(a, b)) {
1272                struct anon_vma *anon_vma = READ_ONCE(old->anon_vma);
1273
1274                if (anon_vma && list_is_singular(&old->anon_vma_chain))
1275                        return anon_vma;
1276        }
1277        return NULL;
1278}
1279
1280/*
1281 * find_mergeable_anon_vma is used by anon_vma_prepare, to check
1282 * neighbouring vmas for a suitable anon_vma, before it goes off
1283 * to allocate a new anon_vma.  It checks because a repetitive
1284 * sequence of mprotects and faults may otherwise lead to distinct
1285 * anon_vmas being allocated, preventing vma merge in subsequent
1286 * mprotect.
1287 */
1288struct anon_vma *find_mergeable_anon_vma(struct vm_area_struct *vma)
1289{
1290        struct anon_vma *anon_vma;
1291        struct vm_area_struct *near;
1292
1293        near = vma->vm_next;
1294        if (!near)
1295                goto try_prev;
1296
1297        anon_vma = reusable_anon_vma(near, vma, near);
1298        if (anon_vma)
1299                return anon_vma;
1300try_prev:
1301        near = vma->vm_prev;
1302        if (!near)
1303                goto none;
1304
1305        anon_vma = reusable_anon_vma(near, near, vma);
1306        if (anon_vma)
1307                return anon_vma;
1308none:
1309        /*
1310         * There's no absolute need to look only at touching neighbours:
1311         * we could search further afield for "compatible" anon_vmas.
1312         * But it would probably just be a waste of time searching,
1313         * or lead to too many vmas hanging off the same anon_vma.
1314         * We're trying to allow mprotect remerging later on,
1315         * not trying to minimize memory used for anon_vmas.
1316         */
1317        return NULL;
1318}
1319
1320/*
1321 * If a hint addr is less than mmap_min_addr change hint to be as
1322 * low as possible but still greater than mmap_min_addr
1323 */
1324static inline unsigned long round_hint_to_min(unsigned long hint)
1325{
1326        hint &= PAGE_MASK;
1327        if (((void *)hint != NULL) &&
1328            (hint < mmap_min_addr))
1329                return PAGE_ALIGN(mmap_min_addr);
1330        return hint;
1331}
1332
1333static inline int mlock_future_check(struct mm_struct *mm,
1334                                     unsigned long flags,
1335                                     unsigned long len)
1336{
1337        unsigned long locked, lock_limit;
1338
1339        /*  mlock MCL_FUTURE? */
1340        if (flags & VM_LOCKED) {
1341                locked = len >> PAGE_SHIFT;
1342                locked += mm->locked_vm;
1343                lock_limit = rlimit(RLIMIT_MEMLOCK);
1344                lock_limit >>= PAGE_SHIFT;
1345                if (locked > lock_limit && !capable(CAP_IPC_LOCK))
1346                        return -EAGAIN;
1347        }
1348        return 0;
1349}
1350
1351static inline u64 file_mmap_size_max(struct file *file, struct inode *inode)
1352{
1353        if (S_ISREG(inode->i_mode))
1354                return MAX_LFS_FILESIZE;
1355
1356        if (S_ISBLK(inode->i_mode))
1357                return MAX_LFS_FILESIZE;
1358
1359        /* Special "we do even unsigned file positions" case */
1360        if (file->f_mode & FMODE_UNSIGNED_OFFSET)
1361                return 0;
1362
1363        /* Yes, random drivers might want more. But I'm tired of buggy drivers */
1364        return ULONG_MAX;
1365}
1366
1367static inline bool file_mmap_ok(struct file *file, struct inode *inode,
1368                                unsigned long pgoff, unsigned long len)
1369{
1370        u64 maxsize = file_mmap_size_max(file, inode);
1371
1372        if (maxsize && len > maxsize)
1373                return false;
1374        maxsize -= len;
1375        if (pgoff > maxsize >> PAGE_SHIFT)
1376                return false;
1377        return true;
1378}
1379
1380/*
1381 * The caller must hold down_write(&current->mm->mmap_sem).
1382 */
1383unsigned long do_mmap(struct file *file, unsigned long addr,
1384                        unsigned long len, unsigned long prot,
1385                        unsigned long flags, vm_flags_t vm_flags,
1386                        unsigned long pgoff, unsigned long *populate,
1387                        struct list_head *uf)
1388{
1389        struct mm_struct *mm = current->mm;
1390        int pkey = 0;
1391
1392        *populate = 0;
1393
1394        if (!len)
1395                return -EINVAL;
1396
1397        /*
1398         * Does the application expect PROT_READ to imply PROT_EXEC?
1399         *
1400         * (the exception is when the underlying filesystem is noexec
1401         *  mounted, in which case we dont add PROT_EXEC.)
1402         */
1403        if ((prot & PROT_READ) && (current->personality & READ_IMPLIES_EXEC))
1404                if (!(file && path_noexec(&file->f_path)))
1405                        prot |= PROT_EXEC;
1406
1407        /* force arch specific MAP_FIXED handling in get_unmapped_area */
1408        if (flags & MAP_FIXED_NOREPLACE)
1409                flags |= MAP_FIXED;
1410
1411        if (!(flags & MAP_FIXED))
1412                addr = round_hint_to_min(addr);
1413
1414        /* Careful about overflows.. */
1415        len = PAGE_ALIGN(len);
1416        if (!len)
1417                return -ENOMEM;
1418
1419        /* offset overflow? */
1420        if ((pgoff + (len >> PAGE_SHIFT)) < pgoff)
1421                return -EOVERFLOW;
1422
1423        /* Too many mappings? */
1424        if (mm->map_count > sysctl_max_map_count)
1425                return -ENOMEM;
1426
1427        /* Obtain the address to map to. we verify (or select) it and ensure
1428         * that it represents a valid section of the address space.
1429         */
1430        addr = get_unmapped_area(file, addr, len, pgoff, flags);
1431        if (offset_in_page(addr))
1432                return addr;
1433
1434        if (flags & MAP_FIXED_NOREPLACE) {
1435                struct vm_area_struct *vma = find_vma(mm, addr);
1436
1437                if (vma && vma->vm_start < addr + len)
1438                        return -EEXIST;
1439        }
1440
1441        if (prot == PROT_EXEC) {
1442                pkey = execute_only_pkey(mm);
1443                if (pkey < 0)
1444                        pkey = 0;
1445        }
1446
1447        /* Do simple checking here so the lower-level routines won't have
1448         * to. we assume access permissions have been handled by the open
1449         * of the memory object, so we don't do any here.
1450         */
1451        vm_flags |= calc_vm_prot_bits(prot, pkey) | calc_vm_flag_bits(flags) |
1452                        mm->def_flags | VM_MAYREAD | VM_MAYWRITE | VM_MAYEXEC;
1453
1454        if (flags & MAP_LOCKED)
1455                if (!can_do_mlock())
1456                        return -EPERM;
1457
1458        if (mlock_future_check(mm, vm_flags, len))
1459                return -EAGAIN;
1460
1461        if (file) {
1462                struct inode *inode = file_inode(file);
1463                unsigned long flags_mask;
1464
1465                if (!file_mmap_ok(file, inode, pgoff, len))
1466                        return -EOVERFLOW;
1467
1468                flags_mask = LEGACY_MAP_MASK | file->f_op->mmap_supported_flags;
1469
1470                switch (flags & MAP_TYPE) {
1471                case MAP_SHARED:
1472                        /*
1473                         * Force use of MAP_SHARED_VALIDATE with non-legacy
1474                         * flags. E.g. MAP_SYNC is dangerous to use with
1475                         * MAP_SHARED as you don't know which consistency model
1476                         * you will get. We silently ignore unsupported flags
1477                         * with MAP_SHARED to preserve backward compatibility.
1478                         */
1479                        flags &= LEGACY_MAP_MASK;
1480                        /* fall through */
1481                case MAP_SHARED_VALIDATE:
1482                        if (flags & ~flags_mask)
1483                                return -EOPNOTSUPP;
1484                        if ((prot&PROT_WRITE) && !(file->f_mode&FMODE_WRITE))
1485                                return -EACCES;
1486
1487                        /*
1488                         * Make sure we don't allow writing to an append-only
1489                         * file..
1490                         */
1491                        if (IS_APPEND(inode) && (file->f_mode & FMODE_WRITE))
1492                                return -EACCES;
1493
1494                        /*
1495                         * Make sure there are no mandatory locks on the file.
1496                         */
1497                        if (locks_verify_locked(file))
1498                                return -EAGAIN;
1499
1500                        vm_flags |= VM_SHARED | VM_MAYSHARE;
1501                        if (!(file->f_mode & FMODE_WRITE))
1502                                vm_flags &= ~(VM_MAYWRITE | VM_SHARED);
1503
1504                        /* fall through */
1505                case MAP_PRIVATE:
1506                        if (!(file->f_mode & FMODE_READ))
1507                                return -EACCES;
1508                        if (path_noexec(&file->f_path)) {
1509                                if (vm_flags & VM_EXEC)
1510                                        return -EPERM;
1511                                vm_flags &= ~VM_MAYEXEC;
1512                        }
1513
1514                        if (!file->f_op->mmap)
1515                                return -ENODEV;
1516                        if (vm_flags & (VM_GROWSDOWN|VM_GROWSUP))
1517                                return -EINVAL;
1518                        break;
1519
1520                default:
1521                        return -EINVAL;
1522                }
1523        } else {
1524                switch (flags & MAP_TYPE) {
1525                case MAP_SHARED:
1526                        if (vm_flags & (VM_GROWSDOWN|VM_GROWSUP))
1527                                return -EINVAL;
1528                        /*
1529                         * Ignore pgoff.
1530                         */
1531                        pgoff = 0;
1532                        vm_flags |= VM_SHARED | VM_MAYSHARE;
1533                        break;
1534                case MAP_PRIVATE:
1535                        /*
1536                         * Set pgoff according to addr for anon_vma.
1537                         */
1538                        pgoff = addr >> PAGE_SHIFT;
1539                        break;
1540                default:
1541                        return -EINVAL;
1542                }
1543        }
1544
1545        /*
1546         * Set 'VM_NORESERVE' if we should not account for the
1547         * memory use of this mapping.
1548         */
1549        if (flags & MAP_NORESERVE) {
1550                /* We honor MAP_NORESERVE if allowed to overcommit */
1551                if (sysctl_overcommit_memory != OVERCOMMIT_NEVER)
1552                        vm_flags |= VM_NORESERVE;
1553
1554                /* hugetlb applies strict overcommit unless MAP_NORESERVE */
1555                if (file && is_file_hugepages(file))
1556                        vm_flags |= VM_NORESERVE;
1557        }
1558
1559        addr = mmap_region(file, addr, len, vm_flags, pgoff, uf);
1560        if (!IS_ERR_VALUE(addr) &&
1561            ((vm_flags & VM_LOCKED) ||
1562             (flags & (MAP_POPULATE | MAP_NONBLOCK)) == MAP_POPULATE))
1563                *populate = len;
1564        return addr;
1565}
1566
1567unsigned long ksys_mmap_pgoff(unsigned long addr, unsigned long len,
1568                              unsigned long prot, unsigned long flags,
1569                              unsigned long fd, unsigned long pgoff)
1570{
1571        struct file *file = NULL;
1572        unsigned long retval;
1573
1574        if (!(flags & MAP_ANONYMOUS)) {
1575                audit_mmap_fd(fd, flags);
1576                file = fget(fd);
1577                if (!file)
1578                        return -EBADF;
1579                if (is_file_hugepages(file))
1580                        len = ALIGN(len, huge_page_size(hstate_file(file)));
1581                retval = -EINVAL;
1582                if (unlikely(flags & MAP_HUGETLB && !is_file_hugepages(file)))
1583                        goto out_fput;
1584        } else if (flags & MAP_HUGETLB) {
1585                struct user_struct *user = NULL;
1586                struct hstate *hs;
1587
1588                hs = hstate_sizelog((flags >> MAP_HUGE_SHIFT) & MAP_HUGE_MASK);
1589                if (!hs)
1590                        return -EINVAL;
1591
1592                len = ALIGN(len, huge_page_size(hs));
1593                /*
1594                 * VM_NORESERVE is used because the reservations will be
1595                 * taken when vm_ops->mmap() is called
1596                 * A dummy user value is used because we are not locking
1597                 * memory so no accounting is necessary
1598                 */
1599                file = hugetlb_file_setup(HUGETLB_ANON_FILE, len,
1600                                VM_NORESERVE,
1601                                &user, HUGETLB_ANONHUGE_INODE,
1602                                (flags >> MAP_HUGE_SHIFT) & MAP_HUGE_MASK);
1603                if (IS_ERR(file))
1604                        return PTR_ERR(file);
1605        }
1606
1607        flags &= ~(MAP_EXECUTABLE | MAP_DENYWRITE);
1608
1609        retval = vm_mmap_pgoff(file, addr, len, prot, flags, pgoff);
1610out_fput:
1611        if (file)
1612                fput(file);
1613        return retval;
1614}
1615
1616SYSCALL_DEFINE6(mmap_pgoff, unsigned long, addr, unsigned long, len,
1617                unsigned long, prot, unsigned long, flags,
1618                unsigned long, fd, unsigned long, pgoff)
1619{
1620        return ksys_mmap_pgoff(addr, len, prot, flags, fd, pgoff);
1621}
1622
1623#ifdef __ARCH_WANT_SYS_OLD_MMAP
1624struct mmap_arg_struct {
1625        unsigned long addr;
1626        unsigned long len;
1627        unsigned long prot;
1628        unsigned long flags;
1629        unsigned long fd;
1630        unsigned long offset;
1631};
1632
1633SYSCALL_DEFINE1(old_mmap, struct mmap_arg_struct __user *, arg)
1634{
1635        struct mmap_arg_struct a;
1636
1637        if (copy_from_user(&a, arg, sizeof(a)))
1638                return -EFAULT;
1639        if (offset_in_page(a.offset))
1640                return -EINVAL;
1641
1642        return ksys_mmap_pgoff(a.addr, a.len, a.prot, a.flags, a.fd,
1643                               a.offset >> PAGE_SHIFT);
1644}
1645#endif /* __ARCH_WANT_SYS_OLD_MMAP */
1646
1647/*
1648 * Some shared mappigns will want the pages marked read-only
1649 * to track write events. If so, we'll downgrade vm_page_prot
1650 * to the private version (using protection_map[] without the
1651 * VM_SHARED bit).
1652 */
1653int vma_wants_writenotify(struct vm_area_struct *vma, pgprot_t vm_page_prot)
1654{
1655        vm_flags_t vm_flags = vma->vm_flags;
1656        const struct vm_operations_struct *vm_ops = vma->vm_ops;
1657
1658        /* If it was private or non-writable, the write bit is already clear */
1659        if ((vm_flags & (VM_WRITE|VM_SHARED)) != ((VM_WRITE|VM_SHARED)))
1660                return 0;
1661
1662        /* The backer wishes to know when pages are first written to? */
1663        if (vm_ops && (vm_ops->page_mkwrite || vm_ops->pfn_mkwrite))
1664                return 1;
1665
1666        /* The open routine did something to the protections that pgprot_modify
1667         * won't preserve? */
1668        if (pgprot_val(vm_page_prot) !=
1669            pgprot_val(vm_pgprot_modify(vm_page_prot, vm_flags)))
1670                return 0;
1671
1672        /* Do we need to track softdirty? */
1673        if (IS_ENABLED(CONFIG_MEM_SOFT_DIRTY) && !(vm_flags & VM_SOFTDIRTY))
1674                return 1;
1675
1676        /* Specialty mapping? */
1677        if (vm_flags & VM_PFNMAP)
1678                return 0;
1679
1680        /* Can the mapping track the dirty pages? */
1681        return vma->vm_file && vma->vm_file->f_mapping &&
1682                mapping_cap_account_dirty(vma->vm_file->f_mapping);
1683}
1684
1685/*
1686 * We account for memory if it's a private writeable mapping,
1687 * not hugepages and VM_NORESERVE wasn't set.
1688 */
1689static inline int accountable_mapping(struct file *file, vm_flags_t vm_flags)
1690{
1691        /*
1692         * hugetlb has its own accounting separate from the core VM
1693         * VM_HUGETLB may not be set yet so we cannot check for that flag.
1694         */
1695        if (file && is_file_hugepages(file))
1696                return 0;
1697
1698        return (vm_flags & (VM_NORESERVE | VM_SHARED | VM_WRITE)) == VM_WRITE;
1699}
1700
1701unsigned long mmap_region(struct file *file, unsigned long addr,
1702                unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
1703                struct list_head *uf)
1704{
1705        struct mm_struct *mm = current->mm;
1706        struct vm_area_struct *vma, *prev;
1707        int error;
1708        struct rb_node **rb_link, *rb_parent;
1709        unsigned long charged = 0;
1710
1711        /* Check against address space limit. */
1712        if (!may_expand_vm(mm, vm_flags, len >> PAGE_SHIFT)) {
1713                unsigned long nr_pages;
1714
1715                /*
1716                 * MAP_FIXED may remove pages of mappings that intersects with
1717                 * requested mapping. Account for the pages it would unmap.
1718                 */
1719                nr_pages = count_vma_pages_range(mm, addr, addr + len);
1720
1721                if (!may_expand_vm(mm, vm_flags,
1722                                        (len >> PAGE_SHIFT) - nr_pages))
1723                        return -ENOMEM;
1724        }
1725
1726        /* Clear old maps */
1727        while (find_vma_links(mm, addr, addr + len, &prev, &rb_link,
1728                              &rb_parent)) {
1729                if (do_munmap(mm, addr, len, uf))
1730                        return -ENOMEM;
1731        }
1732
1733        /*
1734         * Private writable mapping: check memory availability
1735         */
1736        if (accountable_mapping(file, vm_flags)) {
1737                charged = len >> PAGE_SHIFT;
1738                if (security_vm_enough_memory_mm(mm, charged))
1739                        return -ENOMEM;
1740                vm_flags |= VM_ACCOUNT;
1741        }
1742
1743        /*
1744         * Can we just expand an old mapping?
1745         */
1746        vma = vma_merge(mm, prev, addr, addr + len, vm_flags,
1747                        NULL, file, pgoff, NULL, NULL_VM_UFFD_CTX);
1748        if (vma)
1749                goto out;
1750
1751        /*
1752         * Determine the object being mapped and call the appropriate
1753         * specific mapper. the address has already been validated, but
1754         * not unmapped, but the maps are removed from the list.
1755         */
1756        vma = vm_area_alloc(mm);
1757        if (!vma) {
1758                error = -ENOMEM;
1759                goto unacct_error;
1760        }
1761
1762        vma->vm_start = addr;
1763        vma->vm_end = addr + len;
1764        vma->vm_flags = vm_flags;
1765        vma->vm_page_prot = vm_get_page_prot(vm_flags);
1766        vma->vm_pgoff = pgoff;
1767
1768        if (file) {
1769                if (vm_flags & VM_DENYWRITE) {
1770                        error = deny_write_access(file);
1771                        if (error)
1772                                goto free_vma;
1773                }
1774                if (vm_flags & VM_SHARED) {
1775                        error = mapping_map_writable(file->f_mapping);
1776                        if (error)
1777                                goto allow_write_and_free_vma;
1778                }
1779
1780                /* ->mmap() can change vma->vm_file, but must guarantee that
1781                 * vma_link() below can deny write-access if VM_DENYWRITE is set
1782                 * and map writably if VM_SHARED is set. This usually means the
1783                 * new file must not have been exposed to user-space, yet.
1784                 */
1785                vma->vm_file = get_file(file);
1786                error = call_mmap(file, vma);
1787                if (error)
1788                        goto unmap_and_free_vma;
1789
1790                /* Can addr have changed??
1791                 *
1792                 * Answer: Yes, several device drivers can do it in their
1793                 *         f_op->mmap method. -DaveM
1794                 * Bug: If addr is changed, prev, rb_link, rb_parent should
1795                 *      be updated for vma_link()
1796                 */
1797                WARN_ON_ONCE(addr != vma->vm_start);
1798
1799                addr = vma->vm_start;
1800                vm_flags = vma->vm_flags;
1801        } else if (vm_flags & VM_SHARED) {
1802                error = shmem_zero_setup(vma);
1803                if (error)
1804                        goto free_vma;
1805        } else {
1806                vma_set_anonymous(vma);
1807        }
1808
1809        vma_link(mm, vma, prev, rb_link, rb_parent);
1810        /* Once vma denies write, undo our temporary denial count */
1811        if (file) {
1812                if (vm_flags & VM_SHARED)
1813                        mapping_unmap_writable(file->f_mapping);
1814                if (vm_flags & VM_DENYWRITE)
1815                        allow_write_access(file);
1816        }
1817        file = vma->vm_file;
1818out:
1819        perf_event_mmap(vma);
1820
1821        vm_stat_account(mm, vm_flags, len >> PAGE_SHIFT);
1822        if (vm_flags & VM_LOCKED) {
1823                if ((vm_flags & VM_SPECIAL) || vma_is_dax(vma) ||
1824                                        is_vm_hugetlb_page(vma) ||
1825                                        vma == get_gate_vma(current->mm))
1826                        vma->vm_flags &= VM_LOCKED_CLEAR_MASK;
1827                else
1828                        mm->locked_vm += (len >> PAGE_SHIFT);
1829        }
1830
1831        if (file)
1832                uprobe_mmap(vma);
1833
1834        /*
1835         * New (or expanded) vma always get soft dirty status.
1836         * Otherwise user-space soft-dirty page tracker won't
1837         * be able to distinguish situation when vma area unmapped,
1838         * then new mapped in-place (which must be aimed as
1839         * a completely new data area).
1840         */
1841        vma->vm_flags |= VM_SOFTDIRTY;
1842
1843        vma_set_page_prot(vma);
1844
1845        return addr;
1846
1847unmap_and_free_vma:
1848        vma->vm_file = NULL;
1849        fput(file);
1850
1851        /* Undo any partial mapping done by a device driver. */
1852        unmap_region(mm, vma, prev, vma->vm_start, vma->vm_end);
1853        charged = 0;
1854        if (vm_flags & VM_SHARED)
1855                mapping_unmap_writable(file->f_mapping);
1856allow_write_and_free_vma:
1857        if (vm_flags & VM_DENYWRITE)
1858                allow_write_access(file);
1859free_vma:
1860        vm_area_free(vma);
1861unacct_error:
1862        if (charged)
1863                vm_unacct_memory(charged);
1864        return error;
1865}
1866
1867unsigned long unmapped_area(struct vm_unmapped_area_info *info)
1868{
1869        /*
1870         * We implement the search by looking for an rbtree node that
1871         * immediately follows a suitable gap. That is,
1872         * - gap_start = vma->vm_prev->vm_end <= info->high_limit - length;
1873         * - gap_end   = vma->vm_start        >= info->low_limit  + length;
1874         * - gap_end - gap_start >= length
1875         */
1876
1877        struct mm_struct *mm = current->mm;
1878        struct vm_area_struct *vma;
1879        unsigned long length, low_limit, high_limit, gap_start, gap_end;
1880
1881        /* Adjust search length to account for worst case alignment overhead */
1882        length = info->length + info->align_mask;
1883        if (length < info->length)
1884                return -ENOMEM;
1885
1886        /* Adjust search limits by the desired length */
1887        if (info->high_limit < length)
1888                return -ENOMEM;
1889        high_limit = info->high_limit - length;
1890
1891        if (info->low_limit > high_limit)
1892                return -ENOMEM;
1893        low_limit = info->low_limit + length;
1894
1895        /* Check if rbtree root looks promising */
1896        if (RB_EMPTY_ROOT(&mm->mm_rb))
1897                goto check_highest;
1898        vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
1899        if (vma->rb_subtree_gap < length)
1900                goto check_highest;
1901
1902        while (true) {
1903                /* Visit left subtree if it looks promising */
1904                gap_end = vm_start_gap(vma);
1905                if (gap_end >= low_limit && vma->vm_rb.rb_left) {
1906                        struct vm_area_struct *left =
1907                                rb_entry(vma->vm_rb.rb_left,
1908                                         struct vm_area_struct, vm_rb);
1909                        if (left->rb_subtree_gap >= length) {
1910                                vma = left;
1911                                continue;
1912                        }
1913                }
1914
1915                gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
1916check_current:
1917                /* Check if current node has a suitable gap */
1918                if (gap_start > high_limit)
1919                        return -ENOMEM;
1920                if (gap_end >= low_limit &&
1921                    gap_end > gap_start && gap_end - gap_start >= length)
1922                        goto found;
1923
1924                /* Visit right subtree if it looks promising */
1925                if (vma->vm_rb.rb_right) {
1926                        struct vm_area_struct *right =
1927                                rb_entry(vma->vm_rb.rb_right,
1928                                         struct vm_area_struct, vm_rb);
1929                        if (right->rb_subtree_gap >= length) {
1930                                vma = right;
1931                                continue;
1932                        }
1933                }
1934
1935                /* Go back up the rbtree to find next candidate node */
1936                while (true) {
1937                        struct rb_node *prev = &vma->vm_rb;
1938                        if (!rb_parent(prev))
1939                                goto check_highest;
1940                        vma = rb_entry(rb_parent(prev),
1941                                       struct vm_area_struct, vm_rb);
1942                        if (prev == vma->vm_rb.rb_left) {
1943                                gap_start = vm_end_gap(vma->vm_prev);
1944                                gap_end = vm_start_gap(vma);
1945                                goto check_current;
1946                        }
1947                }
1948        }
1949
1950check_highest:
1951        /* Check highest gap, which does not precede any rbtree node */
1952        gap_start = mm->highest_vm_end;
1953        gap_end = ULONG_MAX;  /* Only for VM_BUG_ON below */
1954        if (gap_start > high_limit)
1955                return -ENOMEM;
1956
1957found:
1958        /* We found a suitable gap. Clip it with the original low_limit. */
1959        if (gap_start < info->low_limit)
1960                gap_start = info->low_limit;
1961
1962        /* Adjust gap address to the desired alignment */
1963        gap_start += (info->align_offset - gap_start) & info->align_mask;
1964
1965        VM_BUG_ON(gap_start + info->length > info->high_limit);
1966        VM_BUG_ON(gap_start + info->length > gap_end);
1967        return gap_start;
1968}
1969
1970unsigned long unmapped_area_topdown(struct vm_unmapped_area_info *info)
1971{
1972        struct mm_struct *mm = current->mm;
1973        struct vm_area_struct *vma;
1974        unsigned long length, low_limit, high_limit, gap_start, gap_end;
1975
1976        /* Adjust search length to account for worst case alignment overhead */
1977        length = info->length + info->align_mask;
1978        if (length < info->length)
1979                return -ENOMEM;
1980
1981        /*
1982         * Adjust search limits by the desired length.
1983         * See implementation comment at top of unmapped_area().
1984         */
1985        gap_end = info->high_limit;
1986        if (gap_end < length)
1987                return -ENOMEM;
1988        high_limit = gap_end - length;
1989
1990        if (info->low_limit > high_limit)
1991                return -ENOMEM;
1992        low_limit = info->low_limit + length;
1993
1994        /* Check highest gap, which does not precede any rbtree node */
1995        gap_start = mm->highest_vm_end;
1996        if (gap_start <= high_limit)
1997                goto found_highest;
1998
1999        /* Check if rbtree root looks promising */
2000        if (RB_EMPTY_ROOT(&mm->mm_rb))
2001                return -ENOMEM;
2002        vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
2003        if (vma->rb_subtree_gap < length)
2004                return -ENOMEM;
2005
2006        while (true) {
2007                /* Visit right subtree if it looks promising */
2008                gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
2009                if (gap_start <= high_limit && vma->vm_rb.rb_right) {
2010                        struct vm_area_struct *right =
2011                                rb_entry(vma->vm_rb.rb_right,
2012                                         struct vm_area_struct, vm_rb);
2013                        if (right->rb_subtree_gap >= length) {
2014                                vma = right;
2015                                continue;
2016                        }
2017                }
2018
2019check_current:
2020                /* Check if current node has a suitable gap */
2021                gap_end = vm_start_gap(vma);
2022                if (gap_end < low_limit)
2023                        return -ENOMEM;
2024                if (gap_start <= high_limit &&
2025                    gap_end > gap_start && gap_end - gap_start >= length)
2026                        goto found;
2027
2028                /* Visit left subtree if it looks promising */
2029                if (vma->vm_rb.rb_left) {
2030                        struct vm_area_struct *left =
2031                                rb_entry(vma->vm_rb.rb_left,
2032                                         struct vm_area_struct, vm_rb);
2033                        if (left->rb_subtree_gap >= length) {
2034                                vma = left;
2035                                continue;
2036                        }
2037                }
2038
2039                /* Go back up the rbtree to find next candidate node */
2040                while (true) {
2041                        struct rb_node *prev = &vma->vm_rb;
2042                        if (!rb_parent(prev))
2043                                return -ENOMEM;
2044                        vma = rb_entry(rb_parent(prev),
2045                                       struct vm_area_struct, vm_rb);
2046                        if (prev == vma->vm_rb.rb_right) {
2047                                gap_start = vma->vm_prev ?
2048                                        vm_end_gap(vma->vm_prev) : 0;
2049                                goto check_current;
2050                        }
2051                }
2052        }
2053
2054found:
2055        /* We found a suitable gap. Clip it with the original high_limit. */
2056        if (gap_end > info->high_limit)
2057                gap_end = info->high_limit;
2058
2059found_highest:
2060        /* Compute highest gap address at the desired alignment */
2061        gap_end -= info->length;
2062        gap_end -= (gap_end - info->align_offset) & info->align_mask;
2063
2064        VM_BUG_ON(gap_end < info->low_limit);
2065        VM_BUG_ON(gap_end < gap_start);
2066        return gap_end;
2067}
2068
2069/* Get an address range which is currently unmapped.
2070 * For shmat() with addr=0.
2071 *
2072 * Ugly calling convention alert:
2073 * Return value with the low bits set means error value,
2074 * ie
2075 *      if (ret & ~PAGE_MASK)
2076 *              error = ret;
2077 *
2078 * This function "knows" that -ENOMEM has the bits set.
2079 */
2080#ifndef HAVE_ARCH_UNMAPPED_AREA
2081unsigned long
2082arch_get_unmapped_area(struct file *filp, unsigned long addr,
2083                unsigned long len, unsigned long pgoff, unsigned long flags)
2084{
2085        struct mm_struct *mm = current->mm;
2086        struct vm_area_struct *vma, *prev;
2087        struct vm_unmapped_area_info info;
2088
2089        if (len > TASK_SIZE - mmap_min_addr)
2090                return -ENOMEM;
2091
2092        if (flags & MAP_FIXED)
2093                return addr;
2094
2095        if (addr) {
2096                addr = PAGE_ALIGN(addr);
2097                vma = find_vma_prev(mm, addr, &prev);
2098                if (TASK_SIZE - len >= addr && addr >= mmap_min_addr &&
2099                    (!vma || addr + len <= vm_start_gap(vma)) &&
2100                    (!prev || addr >= vm_end_gap(prev)))
2101                        return addr;
2102        }
2103
2104        info.flags = 0;
2105        info.length = len;
2106        info.low_limit = mm->mmap_base;
2107        info.high_limit = TASK_SIZE;
2108        info.align_mask = 0;
2109        return vm_unmapped_area(&info);
2110}
2111#endif
2112
2113/*
2114 * This mmap-allocator allocates new areas top-down from below the
2115 * stack's low limit (the base):
2116 */
2117#ifndef HAVE_ARCH_UNMAPPED_AREA_TOPDOWN
2118unsigned long
2119arch_get_unmapped_area_topdown(struct file *filp, const unsigned long addr0,
2120                          const unsigned long len, const unsigned long pgoff,
2121                          const unsigned long flags)
2122{
2123        struct vm_area_struct *vma, *prev;
2124        struct mm_struct *mm = current->mm;
2125        unsigned long addr = addr0;
2126        struct vm_unmapped_area_info info;
2127
2128        /* requested length too big for entire address space */
2129        if (len > TASK_SIZE - mmap_min_addr)
2130                return -ENOMEM;
2131
2132        if (flags & MAP_FIXED)
2133                return addr;
2134
2135        /* requesting a specific address */
2136        if (addr) {
2137                addr = PAGE_ALIGN(addr);
2138                vma = find_vma_prev(mm, addr, &prev);
2139                if (TASK_SIZE - len >= addr && addr >= mmap_min_addr &&
2140                                (!vma || addr + len <= vm_start_gap(vma)) &&
2141                                (!prev || addr >= vm_end_gap(prev)))
2142                        return addr;
2143        }
2144
2145        info.flags = VM_UNMAPPED_AREA_TOPDOWN;
2146        info.length = len;
2147        info.low_limit = max(PAGE_SIZE, mmap_min_addr);
2148        info.high_limit = mm->mmap_base;
2149        info.align_mask = 0;
2150        addr = vm_unmapped_area(&info);
2151
2152        /*
2153         * A failed mmap() very likely causes application failure,
2154         * so fall back to the bottom-up function here. This scenario
2155         * can happen with large stack limits and large mmap()
2156         * allocations.
2157         */
2158        if (offset_in_page(addr)) {
2159                VM_BUG_ON(addr != -ENOMEM);
2160                info.flags = 0;
2161                info.low_limit = TASK_UNMAPPED_BASE;
2162                info.high_limit = TASK_SIZE;
2163                addr = vm_unmapped_area(&info);
2164        }
2165
2166        return addr;
2167}
2168#endif
2169
2170unsigned long
2171get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
2172                unsigned long pgoff, unsigned long flags)
2173{
2174        unsigned long (*get_area)(struct file *, unsigned long,
2175                                  unsigned long, unsigned long, unsigned long);
2176
2177        unsigned long error = arch_mmap_check(addr, len, flags);
2178        if (error)
2179                return error;
2180
2181        /* Careful about overflows.. */
2182        if (len > TASK_SIZE)
2183                return -ENOMEM;
2184
2185        get_area = current->mm->get_unmapped_area;
2186        if (file) {
2187                if (file->f_op->get_unmapped_area)
2188                        get_area = file->f_op->get_unmapped_area;
2189        } else if (flags & MAP_SHARED) {
2190                /*
2191                 * mmap_region() will call shmem_zero_setup() to create a file,
2192                 * so use shmem's get_unmapped_area in case it can be huge.
2193                 * do_mmap_pgoff() will clear pgoff, so match alignment.
2194                 */
2195                pgoff = 0;
2196                get_area = shmem_get_unmapped_area;
2197        }
2198
2199        addr = get_area(file, addr, len, pgoff, flags);
2200        if (IS_ERR_VALUE(addr))
2201                return addr;
2202
2203        if (addr > TASK_SIZE - len)
2204                return -ENOMEM;
2205        if (offset_in_page(addr))
2206                return -EINVAL;
2207
2208        error = security_mmap_addr(addr);
2209        return error ? error : addr;
2210}
2211
2212EXPORT_SYMBOL(get_unmapped_area);
2213
2214/* Look up the first VMA which satisfies  addr < vm_end,  NULL if none. */
2215struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
2216{
2217        struct rb_node *rb_node;
2218        struct vm_area_struct *vma;
2219
2220        /* Check the cache first. */
2221        vma = vmacache_find(mm, addr);
2222        if (likely(vma))
2223                return vma;
2224
2225        rb_node = mm->mm_rb.rb_node;
2226
2227        while (rb_node) {
2228                struct vm_area_struct *tmp;
2229
2230                tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
2231
2232                if (tmp->vm_end > addr) {
2233                        vma = tmp;
2234                        if (tmp->vm_start <= addr)
2235                                break;
2236                        rb_node = rb_node->rb_left;
2237                } else
2238                        rb_node = rb_node->rb_right;
2239        }
2240
2241        if (vma)
2242                vmacache_update(addr, vma);
2243        return vma;
2244}
2245
2246EXPORT_SYMBOL(find_vma);
2247
2248/*
2249 * Same as find_vma, but also return a pointer to the previous VMA in *pprev.
2250 */
2251struct vm_area_struct *
2252find_vma_prev(struct mm_struct *mm, unsigned long addr,
2253                        struct vm_area_struct **pprev)
2254{
2255        struct vm_area_struct *vma;
2256
2257        vma = find_vma(mm, addr);
2258        if (vma) {
2259                *pprev = vma->vm_prev;
2260        } else {
2261                struct rb_node *rb_node = mm->mm_rb.rb_node;
2262                *pprev = NULL;
2263                while (rb_node) {
2264                        *pprev = rb_entry(rb_node, struct vm_area_struct, vm_rb);
2265                        rb_node = rb_node->rb_right;
2266                }
2267        }
2268        return vma;
2269}
2270
2271/*
2272 * Verify that the stack growth is acceptable and
2273 * update accounting. This is shared with both the
2274 * grow-up and grow-down cases.
2275 */
2276static int acct_stack_growth(struct vm_area_struct *vma,
2277                             unsigned long size, unsigned long grow)
2278{
2279        struct mm_struct *mm = vma->vm_mm;
2280        unsigned long new_start;
2281
2282        /* address space limit tests */
2283        if (!may_expand_vm(mm, vma->vm_flags, grow))
2284                return -ENOMEM;
2285
2286        /* Stack limit test */
2287        if (size > rlimit(RLIMIT_STACK))
2288                return -ENOMEM;
2289
2290        /* mlock limit tests */
2291        if (vma->vm_flags & VM_LOCKED) {
2292                unsigned long locked;
2293                unsigned long limit;
2294                locked = mm->locked_vm + grow;
2295                limit = rlimit(RLIMIT_MEMLOCK);
2296                limit >>= PAGE_SHIFT;
2297                if (locked > limit && !capable(CAP_IPC_LOCK))
2298                        return -ENOMEM;
2299        }
2300
2301        /* Check to ensure the stack will not grow into a hugetlb-only region */
2302        new_start = (vma->vm_flags & VM_GROWSUP) ? vma->vm_start :
2303                        vma->vm_end - size;
2304        if (is_hugepage_only_range(vma->vm_mm, new_start, size))
2305                return -EFAULT;
2306
2307        /*
2308         * Overcommit..  This must be the final test, as it will
2309         * update security statistics.
2310         */
2311        if (security_vm_enough_memory_mm(mm, grow))
2312                return -ENOMEM;
2313
2314        return 0;
2315}
2316
2317#if defined(CONFIG_STACK_GROWSUP) || defined(CONFIG_IA64)
2318/*
2319 * PA-RISC uses this for its stack; IA64 for its Register Backing Store.
2320 * vma is the last one with address > vma->vm_end.  Have to extend vma.
2321 */
2322int expand_upwards(struct vm_area_struct *vma, unsigned long address)
2323{
2324        struct mm_struct *mm = vma->vm_mm;
2325        struct vm_area_struct *next;
2326        unsigned long gap_addr;
2327        int error = 0;
2328
2329        if (!(vma->vm_flags & VM_GROWSUP))
2330                return -EFAULT;
2331
2332        /* Guard against exceeding limits of the address space. */
2333        address &= PAGE_MASK;
2334        if (address >= (TASK_SIZE & PAGE_MASK))
2335                return -ENOMEM;
2336        address += PAGE_SIZE;
2337
2338        /* Enforce stack_guard_gap */
2339        gap_addr = address + stack_guard_gap;
2340
2341        /* Guard against overflow */
2342        if (gap_addr < address || gap_addr > TASK_SIZE)
2343                gap_addr = TASK_SIZE;
2344
2345        next = vma->vm_next;
2346        if (next && next->vm_start < gap_addr &&
2347                        (next->vm_flags & (VM_WRITE|VM_READ|VM_EXEC))) {
2348                if (!(next->vm_flags & VM_GROWSUP))
2349                        return -ENOMEM;
2350                /* Check that both stack segments have the same anon_vma? */
2351        }
2352
2353        /* We must make sure the anon_vma is allocated. */
2354        if (unlikely(anon_vma_prepare(vma)))
2355                return -ENOMEM;
2356
2357        /*
2358         * vma->vm_start/vm_end cannot change under us because the caller
2359         * is required to hold the mmap_sem in read mode.  We need the
2360         * anon_vma lock to serialize against concurrent expand_stacks.
2361         */
2362        anon_vma_lock_write(vma->anon_vma);
2363
2364        /* Somebody else might have raced and expanded it already */
2365        if (address > vma->vm_end) {
2366                unsigned long size, grow;
2367
2368                size = address - vma->vm_start;
2369                grow = (address - vma->vm_end) >> PAGE_SHIFT;
2370
2371                error = -ENOMEM;
2372                if (vma->vm_pgoff + (size >> PAGE_SHIFT) >= vma->vm_pgoff) {
2373                        error = acct_stack_growth(vma, size, grow);
2374                        if (!error) {
2375                                /*
2376                                 * vma_gap_update() doesn't support concurrent
2377                                 * updates, but we only hold a shared mmap_sem
2378                                 * lock here, so we need to protect against
2379                                 * concurrent vma expansions.
2380                                 * anon_vma_lock_write() doesn't help here, as
2381                                 * we don't guarantee that all growable vmas
2382                                 * in a mm share the same root anon vma.
2383                                 * So, we reuse mm->page_table_lock to guard
2384                                 * against concurrent vma expansions.
2385                                 */
2386                                spin_lock(&mm->page_table_lock);
2387                                if (vma->vm_flags & VM_LOCKED)
2388                                        mm->locked_vm += grow;
2389                                vm_stat_account(mm, vma->vm_flags, grow);
2390                                anon_vma_interval_tree_pre_update_vma(vma);
2391                                vma->vm_end = address;
2392                                anon_vma_interval_tree_post_update_vma(vma);
2393                                if (vma->vm_next)
2394                                        vma_gap_update(vma->vm_next);
2395                                else
2396                                        mm->highest_vm_end = vm_end_gap(vma);
2397                                spin_unlock(&mm->page_table_lock);
2398
2399                                perf_event_mmap(vma);
2400                        }
2401                }
2402        }
2403        anon_vma_unlock_write(vma->anon_vma);
2404        khugepaged_enter_vma_merge(vma, vma->vm_flags);
2405        validate_mm(mm);
2406        return error;
2407}
2408#endif /* CONFIG_STACK_GROWSUP || CONFIG_IA64 */
2409
2410/*
2411 * vma is the first one with address < vma->vm_start.  Have to extend vma.
2412 */
2413int expand_downwards(struct vm_area_struct *vma,
2414                                   unsigned long address)
2415{
2416        struct mm_struct *mm = vma->vm_mm;
2417        struct vm_area_struct *prev;
2418        int error;
2419
2420        address &= PAGE_MASK;
2421        error = security_mmap_addr(address);
2422        if (error)
2423                return error;
2424
2425        /* Enforce stack_guard_gap */
2426        prev = vma->vm_prev;
2427        /* Check that both stack segments have the same anon_vma? */
2428        if (prev && !(prev->vm_flags & VM_GROWSDOWN) &&
2429                        (prev->vm_flags & (VM_WRITE|VM_READ|VM_EXEC))) {
2430                if (address - prev->vm_end < stack_guard_gap)
2431                        return -ENOMEM;
2432        }
2433
2434        /* We must make sure the anon_vma is allocated. */
2435        if (unlikely(anon_vma_prepare(vma)))
2436                return -ENOMEM;
2437
2438        /*
2439         * vma->vm_start/vm_end cannot change under us because the caller
2440         * is required to hold the mmap_sem in read mode.  We need the
2441         * anon_vma lock to serialize against concurrent expand_stacks.
2442         */
2443        anon_vma_lock_write(vma->anon_vma);
2444
2445        /* Somebody else might have raced and expanded it already */
2446        if (address < vma->vm_start) {
2447                unsigned long size, grow;
2448
2449                size = vma->vm_end - address;
2450                grow = (vma->vm_start - address) >> PAGE_SHIFT;
2451
2452                error = -ENOMEM;
2453                if (grow <= vma->vm_pgoff) {
2454                        error = acct_stack_growth(vma, size, grow);
2455                        if (!error) {
2456                                /*
2457                                 * vma_gap_update() doesn't support concurrent
2458                                 * updates, but we only hold a shared mmap_sem
2459                                 * lock here, so we need to protect against
2460                                 * concurrent vma expansions.
2461                                 * anon_vma_lock_write() doesn't help here, as
2462                                 * we don't guarantee that all growable vmas
2463                                 * in a mm share the same root anon vma.
2464                                 * So, we reuse mm->page_table_lock to guard
2465                                 * against concurrent vma expansions.
2466                                 */
2467                                spin_lock(&mm->page_table_lock);
2468                                if (vma->vm_flags & VM_LOCKED)
2469                                        mm->locked_vm += grow;
2470                                vm_stat_account(mm, vma->vm_flags, grow);
2471                                anon_vma_interval_tree_pre_update_vma(vma);
2472                                vma->vm_start = address;
2473                                vma->vm_pgoff -= grow;
2474                                anon_vma_interval_tree_post_update_vma(vma);
2475                                vma_gap_update(vma);
2476                                spin_unlock(&mm->page_table_lock);
2477
2478                                perf_event_mmap(vma);
2479                        }
2480                }
2481        }
2482        anon_vma_unlock_write(vma->anon_vma);
2483        khugepaged_enter_vma_merge(vma, vma->vm_flags);
2484        validate_mm(mm);
2485        return error;
2486}
2487
2488/* enforced gap between the expanding stack and other mappings. */
2489unsigned long stack_guard_gap = 256UL<<PAGE_SHIFT;
2490
2491static int __init cmdline_parse_stack_guard_gap(char *p)
2492{
2493        unsigned long val;
2494        char *endptr;
2495
2496        val = simple_strtoul(p, &endptr, 10);
2497        if (!*endptr)
2498                stack_guard_gap = val << PAGE_SHIFT;
2499
2500        return 0;
2501}
2502__setup("stack_guard_gap=", cmdline_parse_stack_guard_gap);
2503
2504#ifdef CONFIG_STACK_GROWSUP
2505int expand_stack(struct vm_area_struct *vma, unsigned long address)
2506{
2507        return expand_upwards(vma, address);
2508}
2509
2510struct vm_area_struct *
2511find_extend_vma(struct mm_struct *mm, unsigned long addr)
2512{
2513        struct vm_area_struct *vma, *prev;
2514
2515        addr &= PAGE_MASK;
2516        vma = find_vma_prev(mm, addr, &prev);
2517        if (vma && (vma->vm_start <= addr))
2518                return vma;
2519        if (!prev || expand_stack(prev, addr))
2520                return NULL;
2521        if (prev->vm_flags & VM_LOCKED)
2522                populate_vma_page_range(prev, addr, prev->vm_end, NULL);
2523        return prev;
2524}
2525#else
2526int expand_stack(struct vm_area_struct *vma, unsigned long address)
2527{
2528        return expand_downwards(vma, address);
2529}
2530
2531struct vm_area_struct *
2532find_extend_vma(struct mm_struct *mm, unsigned long addr)
2533{
2534        struct vm_area_struct *vma;
2535        unsigned long start;
2536
2537        addr &= PAGE_MASK;
2538        vma = find_vma(mm, addr);
2539        if (!vma)
2540                return NULL;
2541        if (vma->vm_start <= addr)
2542                return vma;
2543        if (!(vma->vm_flags & VM_GROWSDOWN))
2544                return NULL;
2545        start = vma->vm_start;
2546        if (expand_stack(vma, addr))
2547                return NULL;
2548        if (vma->vm_flags & VM_LOCKED)
2549                populate_vma_page_range(vma, addr, start, NULL);
2550        return vma;
2551}
2552#endif
2553
2554EXPORT_SYMBOL_GPL(find_extend_vma);
2555
2556/*
2557 * Ok - we have the memory areas we should free on the vma list,
2558 * so release them, and do the vma updates.
2559 *
2560 * Called with the mm semaphore held.
2561 */
2562static void remove_vma_list(struct mm_struct *mm, struct vm_area_struct *vma)
2563{
2564        unsigned long nr_accounted = 0;
2565
2566        /* Update high watermark before we lower total_vm */
2567        update_hiwater_vm(mm);
2568        do {
2569                long nrpages = vma_pages(vma);
2570
2571                if (vma->vm_flags & VM_ACCOUNT)
2572                        nr_accounted += nrpages;
2573                vm_stat_account(mm, vma->vm_flags, -nrpages);
2574                vma = remove_vma(vma);
2575        } while (vma);
2576        vm_unacct_memory(nr_accounted);
2577        validate_mm(mm);
2578}
2579
2580/*
2581 * Get rid of page table information in the indicated region.
2582 *
2583 * Called with the mm semaphore held.
2584 */
2585static void unmap_region(struct mm_struct *mm,
2586                struct vm_area_struct *vma, struct vm_area_struct *prev,
2587                unsigned long start, unsigned long end)
2588{
2589        struct vm_area_struct *next = prev ? prev->vm_next : mm->mmap;
2590        struct mmu_gather tlb;
2591
2592        lru_add_drain();
2593        tlb_gather_mmu(&tlb, mm, start, end);
2594        update_hiwater_rss(mm);
2595        unmap_vmas(&tlb, vma, start, end);
2596        free_pgtables(&tlb, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
2597                                 next ? next->vm_start : USER_PGTABLES_CEILING);
2598        tlb_finish_mmu(&tlb, start, end);
2599}
2600
2601/*
2602 * Create a list of vma's touched by the unmap, removing them from the mm's
2603 * vma list as we go..
2604 */
2605static void
2606detach_vmas_to_be_unmapped(struct mm_struct *mm, struct vm_area_struct *vma,
2607        struct vm_area_struct *prev, unsigned long end)
2608{
2609        struct vm_area_struct **insertion_point;
2610        struct vm_area_struct *tail_vma = NULL;
2611
2612        insertion_point = (prev ? &prev->vm_next : &mm->mmap);
2613        vma->vm_prev = NULL;
2614        do {
2615                vma_rb_erase(vma, &mm->mm_rb);
2616                mm->map_count--;
2617                tail_vma = vma;
2618                vma = vma->vm_next;
2619        } while (vma && vma->vm_start < end);
2620        *insertion_point = vma;
2621        if (vma) {
2622                vma->vm_prev = prev;
2623                vma_gap_update(vma);
2624        } else
2625                mm->highest_vm_end = prev ? vm_end_gap(prev) : 0;
2626        tail_vma->vm_next = NULL;
2627
2628        /* Kill the cache */
2629        vmacache_invalidate(mm);
2630}
2631
2632/*
2633 * __split_vma() bypasses sysctl_max_map_count checking.  We use this where it
2634 * has already been checked or doesn't make sense to fail.
2635 */
2636int __split_vma(struct mm_struct *mm, struct vm_area_struct *vma,
2637                unsigned long addr, int new_below)
2638{
2639        struct vm_area_struct *new;
2640        int err;
2641
2642        if (vma->vm_ops && vma->vm_ops->split) {
2643                err = vma->vm_ops->split(vma, addr);
2644                if (err)
2645                        return err;
2646        }
2647
2648        new = vm_area_dup(vma);
2649        if (!new)
2650                return -ENOMEM;
2651
2652        if (new_below)
2653                new->vm_end = addr;
2654        else {
2655                new->vm_start = addr;
2656                new->vm_pgoff += ((addr - vma->vm_start) >> PAGE_SHIFT);
2657        }
2658
2659        err = vma_dup_policy(vma, new);
2660        if (err)
2661                goto out_free_vma;
2662
2663        err = anon_vma_clone(new, vma);
2664        if (err)
2665                goto out_free_mpol;
2666
2667        if (new->vm_file)
2668                get_file(new->vm_file);
2669
2670        if (new->vm_ops && new->vm_ops->open)
2671                new->vm_ops->open(new);
2672
2673        if (new_below)
2674                err = vma_adjust(vma, addr, vma->vm_end, vma->vm_pgoff +
2675                        ((addr - new->vm_start) >> PAGE_SHIFT), new);
2676        else
2677                err = vma_adjust(vma, vma->vm_start, addr, vma->vm_pgoff, new);
2678
2679        /* Success. */
2680        if (!err)
2681                return 0;
2682
2683        /* Clean everything up if vma_adjust failed. */
2684        if (new->vm_ops && new->vm_ops->close)
2685                new->vm_ops->close(new);
2686        if (new->vm_file)
2687                fput(new->vm_file);
2688        unlink_anon_vmas(new);
2689 out_free_mpol:
2690        mpol_put(vma_policy(new));
2691 out_free_vma:
2692        vm_area_free(new);
2693        return err;
2694}
2695
2696/*
2697 * Split a vma into two pieces at address 'addr', a new vma is allocated
2698 * either for the first part or the tail.
2699 */
2700int split_vma(struct mm_struct *mm, struct vm_area_struct *vma,
2701              unsigned long addr, int new_below)
2702{
2703        if (mm->map_count >= sysctl_max_map_count)
2704                return -ENOMEM;
2705
2706        return __split_vma(mm, vma, addr, new_below);
2707}
2708
2709/* Munmap is split into 2 main parts -- this part which finds
2710 * what needs doing, and the areas themselves, which do the
2711 * work.  This now handles partial unmappings.
2712 * Jeremy Fitzhardinge <jeremy@goop.org>
2713 */
2714int __do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
2715                struct list_head *uf, bool downgrade)
2716{
2717        unsigned long end;
2718        struct vm_area_struct *vma, *prev, *last;
2719
2720        if ((offset_in_page(start)) || start > TASK_SIZE || len > TASK_SIZE-start)
2721                return -EINVAL;
2722
2723        len = PAGE_ALIGN(len);
2724        if (len == 0)
2725                return -EINVAL;
2726
2727        /* Find the first overlapping VMA */
2728        vma = find_vma(mm, start);
2729        if (!vma)
2730                return 0;
2731        prev = vma->vm_prev;
2732        /* we have  start < vma->vm_end  */
2733
2734        /* if it doesn't overlap, we have nothing.. */
2735        end = start + len;
2736        if (vma->vm_start >= end)
2737                return 0;
2738
2739        /*
2740         * If we need to split any vma, do it now to save pain later.
2741         *
2742         * Note: mremap's move_vma VM_ACCOUNT handling assumes a partially
2743         * unmapped vm_area_struct will remain in use: so lower split_vma
2744         * places tmp vma above, and higher split_vma places tmp vma below.
2745         */
2746        if (start > vma->vm_start) {
2747                int error;
2748
2749                /*
2750                 * Make sure that map_count on return from munmap() will
2751                 * not exceed its limit; but let map_count go just above
2752                 * its limit temporarily, to help free resources as expected.
2753                 */
2754                if (end < vma->vm_end && mm->map_count >= sysctl_max_map_count)
2755                        return -ENOMEM;
2756
2757                error = __split_vma(mm, vma, start, 0);
2758                if (error)
2759                        return error;
2760                prev = vma;
2761        }
2762
2763        /* Does it split the last one? */
2764        last = find_vma(mm, end);
2765        if (last && end > last->vm_start) {
2766                int error = __split_vma(mm, last, end, 1);
2767                if (error)
2768                        return error;
2769        }
2770        vma = prev ? prev->vm_next : mm->mmap;
2771
2772        if (unlikely(uf)) {
2773                /*
2774                 * If userfaultfd_unmap_prep returns an error the vmas
2775                 * will remain splitted, but userland will get a
2776                 * highly unexpected error anyway. This is no
2777                 * different than the case where the first of the two
2778                 * __split_vma fails, but we don't undo the first
2779                 * split, despite we could. This is unlikely enough
2780                 * failure that it's not worth optimizing it for.
2781                 */
2782                int error = userfaultfd_unmap_prep(vma, start, end, uf);
2783                if (error)
2784                        return error;
2785        }
2786
2787        /*
2788         * unlock any mlock()ed ranges before detaching vmas
2789         */
2790        if (mm->locked_vm) {
2791                struct vm_area_struct *tmp = vma;
2792                while (tmp && tmp->vm_start < end) {
2793                        if (tmp->vm_flags & VM_LOCKED) {
2794                                mm->locked_vm -= vma_pages(tmp);
2795                                munlock_vma_pages_all(tmp);
2796                        }
2797
2798                        tmp = tmp->vm_next;
2799                }
2800        }
2801
2802        /* Detach vmas from rbtree */
2803        detach_vmas_to_be_unmapped(mm, vma, prev, end);
2804
2805        /*
2806         * mpx unmap needs to be called with mmap_sem held for write.
2807         * It is safe to call it before unmap_region().
2808         */
2809        arch_unmap(mm, vma, start, end);
2810
2811        if (downgrade)
2812                downgrade_write(&mm->mmap_sem);
2813
2814        unmap_region(mm, vma, prev, start, end);
2815
2816        /* Fix up all other VM information */
2817        remove_vma_list(mm, vma);
2818
2819        return downgrade ? 1 : 0;
2820}
2821
2822int do_munmap(struct mm_struct *mm, unsigned long start, size_t len,
2823              struct list_head *uf)
2824{
2825        return __do_munmap(mm, start, len, uf, false);
2826}
2827
2828static int __vm_munmap(unsigned long start, size_t len, bool downgrade)
2829{
2830        int ret;
2831        struct mm_struct *mm = current->mm;
2832        LIST_HEAD(uf);
2833
2834        if (down_write_killable(&mm->mmap_sem))
2835                return -EINTR;
2836
2837        ret = __do_munmap(mm, start, len, &uf, downgrade);
2838        /*
2839         * Returning 1 indicates mmap_sem is downgraded.
2840         * But 1 is not legal return value of vm_munmap() and munmap(), reset
2841         * it to 0 before return.
2842         */
2843        if (ret == 1) {
2844                up_read(&mm->mmap_sem);
2845                ret = 0;
2846        } else
2847                up_write(&mm->mmap_sem);
2848
2849        userfaultfd_unmap_complete(mm, &uf);
2850        return ret;
2851}
2852
2853int vm_munmap(unsigned long start, size_t len)
2854{
2855        return __vm_munmap(start, len, false);
2856}
2857EXPORT_SYMBOL(vm_munmap);
2858
2859SYSCALL_DEFINE2(munmap, unsigned long, addr, size_t, len)
2860{
2861        profile_munmap(addr);
2862        return __vm_munmap(addr, len, true);
2863}
2864
2865
2866/*
2867 * Emulation of deprecated remap_file_pages() syscall.
2868 */
2869SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
2870                unsigned long, prot, unsigned long, pgoff, unsigned long, flags)
2871{
2872
2873        struct mm_struct *mm = current->mm;
2874        struct vm_area_struct *vma;
2875        unsigned long populate = 0;
2876        unsigned long ret = -EINVAL;
2877        struct file *file;
2878
2879        pr_warn_once("%s (%d) uses deprecated remap_file_pages() syscall. See Documentation/vm/remap_file_pages.rst.\n",
2880                     current->comm, current->pid);
2881
2882        if (prot)
2883                return ret;
2884        start = start & PAGE_MASK;
2885        size = size & PAGE_MASK;
2886
2887        if (start + size <= start)
2888                return ret;
2889
2890        /* Does pgoff wrap? */
2891        if (pgoff + (size >> PAGE_SHIFT) < pgoff)
2892                return ret;
2893
2894        if (down_write_killable(&mm->mmap_sem))
2895                return -EINTR;
2896
2897        vma = find_vma(mm, start);
2898
2899        if (!vma || !(vma->vm_flags & VM_SHARED))
2900                goto out;
2901
2902        if (start < vma->vm_start)
2903                goto out;
2904
2905        if (start + size > vma->vm_end) {
2906                struct vm_area_struct *next;
2907
2908                for (next = vma->vm_next; next; next = next->vm_next) {
2909                        /* hole between vmas ? */
2910                        if (next->vm_start != next->vm_prev->vm_end)
2911                                goto out;
2912
2913                        if (next->vm_file != vma->vm_file)
2914                                goto out;
2915
2916                        if (next->vm_flags != vma->vm_flags)
2917                                goto out;
2918
2919                        if (start + size <= next->vm_end)
2920                                break;
2921                }
2922
2923                if (!next)
2924                        goto out;
2925        }
2926
2927        prot |= vma->vm_flags & VM_READ ? PROT_READ : 0;
2928        prot |= vma->vm_flags & VM_WRITE ? PROT_WRITE : 0;
2929        prot |= vma->vm_flags & VM_EXEC ? PROT_EXEC : 0;
2930
2931        flags &= MAP_NONBLOCK;
2932        flags |= MAP_SHARED | MAP_FIXED | MAP_POPULATE;
2933        if (vma->vm_flags & VM_LOCKED) {
2934                struct vm_area_struct *tmp;
2935                flags |= MAP_LOCKED;
2936
2937                /* drop PG_Mlocked flag for over-mapped range */
2938                for (tmp = vma; tmp->vm_start >= start + size;
2939                                tmp = tmp->vm_next) {
2940                        /*
2941                         * Split pmd and munlock page on the border
2942                         * of the range.
2943                         */
2944                        vma_adjust_trans_huge(tmp, start, start + size, 0);
2945
2946                        munlock_vma_pages_range(tmp,
2947                                        max(tmp->vm_start, start),
2948                                        min(tmp->vm_end, start + size));
2949                }
2950        }
2951
2952        file = get_file(vma->vm_file);
2953        ret = do_mmap_pgoff(vma->vm_file, start, size,
2954                        prot, flags, pgoff, &populate, NULL);
2955        fput(file);
2956out:
2957        up_write(&mm->mmap_sem);
2958        if (populate)
2959                mm_populate(ret, populate);
2960        if (!IS_ERR_VALUE(ret))
2961                ret = 0;
2962        return ret;
2963}
2964
2965static inline void verify_mm_writelocked(struct mm_struct *mm)
2966{
2967#ifdef CONFIG_DEBUG_VM
2968        if (unlikely(down_read_trylock(&mm->mmap_sem))) {
2969                WARN_ON(1);
2970                up_read(&mm->mmap_sem);
2971        }
2972#endif
2973}
2974
2975/*
2976 *  this is really a simplified "do_mmap".  it only handles
2977 *  anonymous maps.  eventually we may be able to do some
2978 *  brk-specific accounting here.
2979 */
2980static int do_brk_flags(unsigned long addr, unsigned long len, unsigned long flags, struct list_head *uf)
2981{
2982        struct mm_struct *mm = current->mm;
2983        struct vm_area_struct *vma, *prev;
2984        struct rb_node **rb_link, *rb_parent;
2985        pgoff_t pgoff = addr >> PAGE_SHIFT;
2986        int error;
2987
2988        /* Until we need other flags, refuse anything except VM_EXEC. */
2989        if ((flags & (~VM_EXEC)) != 0)
2990                return -EINVAL;
2991        flags |= VM_DATA_DEFAULT_FLAGS | VM_ACCOUNT | mm->def_flags;
2992
2993        error = get_unmapped_area(NULL, addr, len, 0, MAP_FIXED);
2994        if (offset_in_page(error))
2995                return error;
2996
2997        error = mlock_future_check(mm, mm->def_flags, len);
2998        if (error)
2999                return error;
3000
3001        /*
3002         * mm->mmap_sem is required to protect against another thread
3003         * changing the mappings in case we sleep.
3004         */
3005        verify_mm_writelocked(mm);
3006
3007        /*
3008         * Clear old maps.  this also does some error checking for us
3009         */
3010        while (find_vma_links(mm, addr, addr + len, &prev, &rb_link,
3011                              &rb_parent)) {
3012                if (do_munmap(mm, addr, len, uf))
3013                        return -ENOMEM;
3014        }
3015
3016        /* Check against address space limits *after* clearing old maps... */
3017        if (!may_expand_vm(mm, flags, len >> PAGE_SHIFT))
3018                return -ENOMEM;
3019
3020        if (mm->map_count > sysctl_max_map_count)
3021                return -ENOMEM;
3022
3023        if (security_vm_enough_memory_mm(mm, len >> PAGE_SHIFT))
3024                return -ENOMEM;
3025
3026        /* Can we just expand an old private anonymous mapping? */
3027        vma = vma_merge(mm, prev, addr, addr + len, flags,
3028                        NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
3029        if (vma)
3030                goto out;
3031
3032        /*
3033         * create a vma struct for an anonymous mapping
3034         */
3035        vma = vm_area_alloc(mm);
3036        if (!vma) {
3037                vm_unacct_memory(len >> PAGE_SHIFT);
3038                return -ENOMEM;
3039        }
3040
3041        vma_set_anonymous(vma);
3042        vma->vm_start = addr;
3043        vma->vm_end = addr + len;
3044        vma->vm_pgoff = pgoff;
3045        vma->vm_flags = flags;
3046        vma->vm_page_prot = vm_get_page_prot(flags);
3047        vma_link(mm, vma, prev, rb_link, rb_parent);
3048out:
3049        perf_event_mmap(vma);
3050        mm->total_vm += len >> PAGE_SHIFT;
3051        mm->data_vm += len >> PAGE_SHIFT;
3052        if (flags & VM_LOCKED)
3053                mm->locked_vm += (len >> PAGE_SHIFT);
3054        vma->vm_flags |= VM_SOFTDIRTY;
3055        return 0;
3056}
3057
3058int vm_brk_flags(unsigned long addr, unsigned long request, unsigned long flags)
3059{
3060        struct mm_struct *mm = current->mm;
3061        unsigned long len;
3062        int ret;
3063        bool populate;
3064        LIST_HEAD(uf);
3065
3066        len = PAGE_ALIGN(request);
3067        if (len < request)
3068                return -ENOMEM;
3069        if (!len)
3070                return 0;
3071
3072        if (down_write_killable(&mm->mmap_sem))
3073                return -EINTR;
3074
3075        ret = do_brk_flags(addr, len, flags, &uf);
3076        populate = ((mm->def_flags & VM_LOCKED) != 0);
3077        up_write(&mm->mmap_sem);
3078        userfaultfd_unmap_complete(mm, &uf);
3079        if (populate && !ret)
3080                mm_populate(addr, len);
3081        return ret;
3082}
3083EXPORT_SYMBOL(vm_brk_flags);
3084
3085int vm_brk(unsigned long addr, unsigned long len)
3086{
3087        return vm_brk_flags(addr, len, 0);
3088}
3089EXPORT_SYMBOL(vm_brk);
3090
3091/* Release all mmaps. */
3092void exit_mmap(struct mm_struct *mm)
3093{
3094        struct mmu_gather tlb;
3095        struct vm_area_struct *vma;
3096        unsigned long nr_accounted = 0;
3097
3098        /* mm's last user has gone, and its about to be pulled down */
3099        mmu_notifier_release(mm);
3100
3101        if (unlikely(mm_is_oom_victim(mm))) {
3102                /*
3103                 * Manually reap the mm to free as much memory as possible.
3104                 * Then, as the oom reaper does, set MMF_OOM_SKIP to disregard
3105                 * this mm from further consideration.  Taking mm->mmap_sem for
3106                 * write after setting MMF_OOM_SKIP will guarantee that the oom
3107                 * reaper will not run on this mm again after mmap_sem is
3108                 * dropped.
3109                 *
3110                 * Nothing can be holding mm->mmap_sem here and the above call
3111                 * to mmu_notifier_release(mm) ensures mmu notifier callbacks in
3112                 * __oom_reap_task_mm() will not block.
3113                 *
3114                 * This needs to be done before calling munlock_vma_pages_all(),
3115                 * which clears VM_LOCKED, otherwise the oom reaper cannot
3116                 * reliably test it.
3117                 */
3118                (void)__oom_reap_task_mm(mm);
3119
3120                set_bit(MMF_OOM_SKIP, &mm->flags);
3121                down_write(&mm->mmap_sem);
3122                up_write(&mm->mmap_sem);
3123        }
3124
3125        if (mm->locked_vm) {
3126                vma = mm->mmap;
3127                while (vma) {
3128                        if (vma->vm_flags & VM_LOCKED)
3129                                munlock_vma_pages_all(vma);
3130                        vma = vma->vm_next;
3131                }
3132        }
3133
3134        arch_exit_mmap(mm);
3135
3136        vma = mm->mmap;
3137        if (!vma)       /* Can happen if dup_mmap() received an OOM */
3138                return;
3139
3140        lru_add_drain();
3141        flush_cache_mm(mm);
3142        tlb_gather_mmu(&tlb, mm, 0, -1);
3143        /* update_hiwater_rss(mm) here? but nobody should be looking */
3144        /* Use -1 here to ensure all VMAs in the mm are unmapped */
3145        unmap_vmas(&tlb, vma, 0, -1);
3146        free_pgtables(&tlb, vma, FIRST_USER_ADDRESS, USER_PGTABLES_CEILING);
3147        tlb_finish_mmu(&tlb, 0, -1);
3148
3149        /*
3150         * Walk the list again, actually closing and freeing it,
3151         * with preemption enabled, without holding any MM locks.
3152         */
3153        while (vma) {
3154                if (vma->vm_flags & VM_ACCOUNT)
3155                        nr_accounted += vma_pages(vma);
3156                vma = remove_vma(vma);
3157        }
3158        vm_unacct_memory(nr_accounted);
3159}
3160
3161/* Insert vm structure into process list sorted by address
3162 * and into the inode's i_mmap tree.  If vm_file is non-NULL
3163 * then i_mmap_rwsem is taken here.
3164 */
3165int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
3166{
3167        struct vm_area_struct *prev;
3168        struct rb_node **rb_link, *rb_parent;
3169
3170        if (find_vma_links(mm, vma->vm_start, vma->vm_end,
3171                           &prev, &rb_link, &rb_parent))
3172                return -ENOMEM;
3173        if ((vma->vm_flags & VM_ACCOUNT) &&
3174             security_vm_enough_memory_mm(mm, vma_pages(vma)))
3175                return -ENOMEM;
3176
3177        /*
3178         * The vm_pgoff of a purely anonymous vma should be irrelevant
3179         * until its first write fault, when page's anon_vma and index
3180         * are set.  But now set the vm_pgoff it will almost certainly
3181         * end up with (unless mremap moves it elsewhere before that
3182         * first wfault), so /proc/pid/maps tells a consistent story.
3183         *
3184         * By setting it to reflect the virtual start address of the
3185         * vma, merges and splits can happen in a seamless way, just
3186         * using the existing file pgoff checks and manipulations.
3187         * Similarly in do_mmap_pgoff and in do_brk.
3188         */
3189        if (vma_is_anonymous(vma)) {
3190                BUG_ON(vma->anon_vma);
3191                vma->vm_pgoff = vma->vm_start >> PAGE_SHIFT;
3192        }
3193
3194        vma_link(mm, vma, prev, rb_link, rb_parent);
3195        return 0;
3196}
3197
3198/*
3199 * Copy the vma structure to a new location in the same mm,
3200 * prior to moving page table entries, to effect an mremap move.
3201 */
3202struct vm_area_struct *copy_vma(struct vm_area_struct **vmap,
3203        unsigned long addr, unsigned long len, pgoff_t pgoff,
3204        bool *need_rmap_locks)
3205{
3206        struct vm_area_struct *vma = *vmap;
3207        unsigned long vma_start = vma->vm_start;
3208        struct mm_struct *mm = vma->vm_mm;
3209        struct vm_area_struct *new_vma, *prev;
3210        struct rb_node **rb_link, *rb_parent;
3211        bool faulted_in_anon_vma = true;
3212
3213        /*
3214         * If anonymous vma has not yet been faulted, update new pgoff
3215         * to match new location, to increase its chance of merging.
3216         */
3217        if (unlikely(vma_is_anonymous(vma) && !vma->anon_vma)) {
3218                pgoff = addr >> PAGE_SHIFT;
3219                faulted_in_anon_vma = false;
3220        }
3221
3222        if (find_vma_links(mm, addr, addr + len, &prev, &rb_link, &rb_parent))
3223                return NULL;    /* should never get here */
3224        new_vma = vma_merge(mm, prev, addr, addr + len, vma->vm_flags,
3225                            vma->anon_vma, vma->vm_file, pgoff, vma_policy(vma),
3226                            vma->vm_userfaultfd_ctx);
3227        if (new_vma) {
3228                /*
3229                 * Source vma may have been merged into new_vma
3230                 */
3231                if (unlikely(vma_start >= new_vma->vm_start &&
3232                             vma_start < new_vma->vm_end)) {
3233                        /*
3234                         * The only way we can get a vma_merge with
3235                         * self during an mremap is if the vma hasn't
3236                         * been faulted in yet and we were allowed to
3237                         * reset the dst vma->vm_pgoff to the
3238                         * destination address of the mremap to allow
3239                         * the merge to happen. mremap must change the
3240                         * vm_pgoff linearity between src and dst vmas
3241                         * (in turn preventing a vma_merge) to be
3242                         * safe. It is only safe to keep the vm_pgoff
3243                         * linear if there are no pages mapped yet.
3244                         */
3245                        VM_BUG_ON_VMA(faulted_in_anon_vma, new_vma);
3246                        *vmap = vma = new_vma;
3247                }
3248                *need_rmap_locks = (new_vma->vm_pgoff <= vma->vm_pgoff);
3249        } else {
3250                new_vma = vm_area_dup(vma);
3251                if (!new_vma)
3252                        goto out;
3253                new_vma->vm_start = addr;
3254                new_vma->vm_end = addr + len;
3255                new_vma->vm_pgoff = pgoff;
3256                if (vma_dup_policy(vma, new_vma))
3257                        goto out_free_vma;
3258                if (anon_vma_clone(new_vma, vma))
3259                        goto out_free_mempol;
3260                if (new_vma->vm_file)
3261                        get_file(new_vma->vm_file);
3262                if (new_vma->vm_ops && new_vma->vm_ops->open)
3263                        new_vma->vm_ops->open(new_vma);
3264                vma_link(mm, new_vma, prev, rb_link, rb_parent);
3265                *need_rmap_locks = false;
3266        }
3267        return new_vma;
3268
3269out_free_mempol:
3270        mpol_put(vma_policy(new_vma));
3271out_free_vma:
3272        vm_area_free(new_vma);
3273out:
3274        return NULL;
3275}
3276
3277/*
3278 * Return true if the calling process may expand its vm space by the passed
3279 * number of pages
3280 */
3281bool may_expand_vm(struct mm_struct *mm, vm_flags_t flags, unsigned long npages)
3282{
3283        if (mm->total_vm + npages > rlimit(RLIMIT_AS) >> PAGE_SHIFT)
3284                return false;
3285
3286        if (is_data_mapping(flags) &&
3287            mm->data_vm + npages > rlimit(RLIMIT_DATA) >> PAGE_SHIFT) {
3288                /* Workaround for Valgrind */
3289                if (rlimit(RLIMIT_DATA) == 0 &&
3290                    mm->data_vm + npages <= rlimit_max(RLIMIT_DATA) >> PAGE_SHIFT)
3291                        return true;
3292
3293                pr_warn_once("%s (%d): VmData %lu exceed data ulimit %lu. Update limits%s.\n",
3294                             current->comm, current->pid,
3295                             (mm->data_vm + npages) << PAGE_SHIFT,
3296                             rlimit(RLIMIT_DATA),
3297                             ignore_rlimit_data ? "" : " or use boot option ignore_rlimit_data");
3298
3299                if (!ignore_rlimit_data)
3300                        return false;
3301        }
3302
3303        return true;
3304}
3305
3306void vm_stat_account(struct mm_struct *mm, vm_flags_t flags, long npages)
3307{
3308        mm->total_vm += npages;
3309
3310        if (is_exec_mapping(flags))
3311                mm->exec_vm += npages;
3312        else if (is_stack_mapping(flags))
3313                mm->stack_vm += npages;
3314        else if (is_data_mapping(flags))
3315                mm->data_vm += npages;
3316}
3317
3318static vm_fault_t special_mapping_fault(struct vm_fault *vmf);
3319
3320/*
3321 * Having a close hook prevents vma merging regardless of flags.
3322 */
3323static void special_mapping_close(struct vm_area_struct *vma)
3324{
3325}
3326
3327static const char *special_mapping_name(struct vm_area_struct *vma)
3328{
3329        return ((struct vm_special_mapping *)vma->vm_private_data)->name;
3330}
3331
3332static int special_mapping_mremap(struct vm_area_struct *new_vma)
3333{
3334        struct vm_special_mapping *sm = new_vma->vm_private_data;
3335
3336        if (WARN_ON_ONCE(current->mm != new_vma->vm_mm))
3337                return -EFAULT;
3338
3339        if (sm->mremap)
3340                return sm->mremap(sm, new_vma);
3341
3342        return 0;
3343}
3344
3345static const struct vm_operations_struct special_mapping_vmops = {
3346        .close = special_mapping_close,
3347        .fault = special_mapping_fault,
3348        .mremap = special_mapping_mremap,
3349        .name = special_mapping_name,
3350};
3351
3352static const struct vm_operations_struct legacy_special_mapping_vmops = {
3353        .close = special_mapping_close,
3354        .fault = special_mapping_fault,
3355};
3356
3357static vm_fault_t special_mapping_fault(struct vm_fault *vmf)
3358{
3359        struct vm_area_struct *vma = vmf->vma;
3360        pgoff_t pgoff;
3361        struct page **pages;
3362
3363        if (vma->vm_ops == &legacy_special_mapping_vmops) {
3364                pages = vma->vm_private_data;
3365        } else {
3366                struct vm_special_mapping *sm = vma->vm_private_data;
3367
3368                if (sm->fault)
3369                        return sm->fault(sm, vmf->vma, vmf);
3370
3371                pages = sm->pages;
3372        }
3373
3374        for (pgoff = vmf->pgoff; pgoff && *pages; ++pages)
3375                pgoff--;
3376
3377        if (*pages) {
3378                struct page *page = *pages;
3379                get_page(page);
3380                vmf->page = page;
3381                return 0;
3382        }
3383
3384        return VM_FAULT_SIGBUS;
3385}
3386
3387static struct vm_area_struct *__install_special_mapping(
3388        struct mm_struct *mm,
3389        unsigned long addr, unsigned long len,
3390        unsigned long vm_flags, void *priv,
3391        const struct vm_operations_struct *ops)
3392{
3393        int ret;
3394        struct vm_area_struct *vma;
3395
3396        vma = vm_area_alloc(mm);
3397        if (unlikely(vma == NULL))
3398                return ERR_PTR(-ENOMEM);
3399
3400        vma->vm_start = addr;
3401        vma->vm_end = addr + len;
3402
3403        vma->vm_flags = vm_flags | mm->def_flags | VM_DONTEXPAND | VM_SOFTDIRTY;
3404        vma->vm_page_prot = vm_get_page_prot(vma->vm_flags);
3405
3406        vma->vm_ops = ops;
3407        vma->vm_private_data = priv;
3408
3409        ret = insert_vm_struct(mm, vma);
3410        if (ret)
3411                goto out;
3412
3413        vm_stat_account(mm, vma->vm_flags, len >> PAGE_SHIFT);
3414
3415        perf_event_mmap(vma);
3416
3417        return vma;
3418
3419out:
3420        vm_area_free(vma);
3421        return ERR_PTR(ret);
3422}
3423
3424bool vma_is_special_mapping(const struct vm_area_struct *vma,
3425        const struct vm_special_mapping *sm)
3426{
3427        return vma->vm_private_data == sm &&
3428                (vma->vm_ops == &special_mapping_vmops ||
3429                 vma->vm_ops == &legacy_special_mapping_vmops);
3430}
3431
3432/*
3433 * Called with mm->mmap_sem held for writing.
3434 * Insert a new vma covering the given region, with the given flags.
3435 * Its pages are supplied by the given array of struct page *.
3436 * The array can be shorter than len >> PAGE_SHIFT if it's null-terminated.
3437 * The region past the last page supplied will always produce SIGBUS.
3438 * The array pointer and the pages it points to are assumed to stay alive
3439 * for as long as this mapping might exist.
3440 */
3441struct vm_area_struct *_install_special_mapping(
3442        struct mm_struct *mm,
3443        unsigned long addr, unsigned long len,
3444        unsigned long vm_flags, const struct vm_special_mapping *spec)
3445{
3446        return __install_special_mapping(mm, addr, len, vm_flags, (void *)spec,
3447                                        &special_mapping_vmops);
3448}
3449
3450int install_special_mapping(struct mm_struct *mm,
3451                            unsigned long addr, unsigned long len,
3452                            unsigned long vm_flags, struct page **pages)
3453{
3454        struct vm_area_struct *vma = __install_special_mapping(
3455                mm, addr, len, vm_flags, (void *)pages,
3456                &legacy_special_mapping_vmops);
3457
3458        return PTR_ERR_OR_ZERO(vma);
3459}
3460
3461static DEFINE_MUTEX(mm_all_locks_mutex);
3462
3463static void vm_lock_anon_vma(struct mm_struct *mm, struct anon_vma *anon_vma)
3464{
3465        if (!test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_root.rb_node)) {
3466                /*
3467                 * The LSB of head.next can't change from under us
3468                 * because we hold the mm_all_locks_mutex.
3469                 */
3470                down_write_nest_lock(&anon_vma->root->rwsem, &mm->mmap_sem);
3471                /*
3472                 * We can safely modify head.next after taking the
3473                 * anon_vma->root->rwsem. If some other vma in this mm shares
3474                 * the same anon_vma we won't take it again.
3475                 *
3476                 * No need of atomic instructions here, head.next
3477                 * can't change from under us thanks to the
3478                 * anon_vma->root->rwsem.
3479                 */
3480                if (__test_and_set_bit(0, (unsigned long *)
3481                                       &anon_vma->root->rb_root.rb_root.rb_node))
3482                        BUG();
3483        }
3484}
3485
3486static void vm_lock_mapping(struct mm_struct *mm, struct address_space *mapping)
3487{
3488        if (!test_bit(AS_MM_ALL_LOCKS, &mapping->flags)) {
3489                /*
3490                 * AS_MM_ALL_LOCKS can't change from under us because
3491                 * we hold the mm_all_locks_mutex.
3492                 *
3493                 * Operations on ->flags have to be atomic because
3494                 * even if AS_MM_ALL_LOCKS is stable thanks to the
3495                 * mm_all_locks_mutex, there may be other cpus
3496                 * changing other bitflags in parallel to us.
3497                 */
3498                if (test_and_set_bit(AS_MM_ALL_LOCKS, &mapping->flags))
3499                        BUG();
3500                down_write_nest_lock(&mapping->i_mmap_rwsem, &mm->mmap_sem);
3501        }
3502}
3503
3504/*
3505 * This operation locks against the VM for all pte/vma/mm related
3506 * operations that could ever happen on a certain mm. This includes
3507 * vmtruncate, try_to_unmap, and all page faults.
3508 *
3509 * The caller must take the mmap_sem in write mode before calling
3510 * mm_take_all_locks(). The caller isn't allowed to release the
3511 * mmap_sem until mm_drop_all_locks() returns.
3512 *
3513 * mmap_sem in write mode is required in order to block all operations
3514 * that could modify pagetables and free pages without need of
3515 * altering the vma layout. It's also needed in write mode to avoid new
3516 * anon_vmas to be associated with existing vmas.
3517 *
3518 * A single task can't take more than one mm_take_all_locks() in a row
3519 * or it would deadlock.
3520 *
3521 * The LSB in anon_vma->rb_root.rb_node and the AS_MM_ALL_LOCKS bitflag in
3522 * mapping->flags avoid to take the same lock twice, if more than one
3523 * vma in this mm is backed by the same anon_vma or address_space.
3524 *
3525 * We take locks in following order, accordingly to comment at beginning
3526 * of mm/rmap.c:
3527 *   - all hugetlbfs_i_mmap_rwsem_key locks (aka mapping->i_mmap_rwsem for
3528 *     hugetlb mapping);
3529 *   - all i_mmap_rwsem locks;
3530 *   - all anon_vma->rwseml
3531 *
3532 * We can take all locks within these types randomly because the VM code
3533 * doesn't nest them and we protected from parallel mm_take_all_locks() by
3534 * mm_all_locks_mutex.
3535 *
3536 * mm_take_all_locks() and mm_drop_all_locks are expensive operations
3537 * that may have to take thousand of locks.
3538 *
3539 * mm_take_all_locks() can fail if it's interrupted by signals.
3540 */
3541int mm_take_all_locks(struct mm_struct *mm)
3542{
3543        struct vm_area_struct *vma;
3544        struct anon_vma_chain *avc;
3545
3546        BUG_ON(down_read_trylock(&mm->mmap_sem));
3547
3548        mutex_lock(&mm_all_locks_mutex);
3549
3550        for (vma = mm->mmap; vma; vma = vma->vm_next) {
3551                if (signal_pending(current))
3552                        goto out_unlock;
3553                if (vma->vm_file && vma->vm_file->f_mapping &&
3554                                is_vm_hugetlb_page(vma))
3555                        vm_lock_mapping(mm, vma->vm_file->f_mapping);
3556        }
3557
3558        for (vma = mm->mmap; vma; vma = vma->vm_next) {
3559                if (signal_pending(current))
3560                        goto out_unlock;
3561                if (vma->vm_file && vma->vm_file->f_mapping &&
3562                                !is_vm_hugetlb_page(vma))
3563                        vm_lock_mapping(mm, vma->vm_file->f_mapping);
3564        }
3565
3566        for (vma = mm->mmap; vma; vma = vma->vm_next) {
3567                if (signal_pending(current))
3568                        goto out_unlock;
3569                if (vma->anon_vma)
3570                        list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
3571                                vm_lock_anon_vma(mm, avc->anon_vma);
3572        }
3573
3574        return 0;
3575
3576out_unlock:
3577        mm_drop_all_locks(mm);
3578        return -EINTR;
3579}
3580
3581static void vm_unlock_anon_vma(struct anon_vma *anon_vma)
3582{
3583        if (test_bit(0, (unsigned long *) &anon_vma->root->rb_root.rb_root.rb_node)) {
3584                /*
3585                 * The LSB of head.next can't change to 0 from under
3586                 * us because we hold the mm_all_locks_mutex.
3587                 *
3588                 * We must however clear the bitflag before unlocking
3589                 * the vma so the users using the anon_vma->rb_root will
3590                 * never see our bitflag.
3591                 *
3592                 * No need of atomic instructions here, head.next
3593                 * can't change from under us until we release the
3594                 * anon_vma->root->rwsem.
3595                 */
3596                if (!__test_and_clear_bit(0, (unsigned long *)
3597                                          &anon_vma->root->rb_root.rb_root.rb_node))
3598                        BUG();
3599                anon_vma_unlock_write(anon_vma);
3600        }
3601}
3602
3603static void vm_unlock_mapping(struct address_space *mapping)
3604{
3605        if (test_bit(AS_MM_ALL_LOCKS, &mapping->flags)) {
3606                /*
3607                 * AS_MM_ALL_LOCKS can't change to 0 from under us
3608                 * because we hold the mm_all_locks_mutex.
3609                 */
3610                i_mmap_unlock_write(mapping);
3611                if (!test_and_clear_bit(AS_MM_ALL_LOCKS,
3612                                        &mapping->flags))
3613                        BUG();
3614        }
3615}
3616
3617/*
3618 * The mmap_sem cannot be released by the caller until
3619 * mm_drop_all_locks() returns.
3620 */
3621void mm_drop_all_locks(struct mm_struct *mm)
3622{
3623        struct vm_area_struct *vma;
3624        struct anon_vma_chain *avc;
3625
3626        BUG_ON(down_read_trylock(&mm->mmap_sem));
3627        BUG_ON(!mutex_is_locked(&mm_all_locks_mutex));
3628
3629        for (vma = mm->mmap; vma; vma = vma->vm_next) {
3630                if (vma->anon_vma)
3631                        list_for_each_entry(avc, &vma->anon_vma_chain, same_vma)
3632                                vm_unlock_anon_vma(avc->anon_vma);
3633                if (vma->vm_file && vma->vm_file->f_mapping)
3634                        vm_unlock_mapping(vma->vm_file->f_mapping);
3635        }
3636
3637        mutex_unlock(&mm_all_locks_mutex);
3638}
3639
3640/*
3641 * initialise the percpu counter for VM
3642 */
3643void __init mmap_init(void)
3644{
3645        int ret;
3646
3647        ret = percpu_counter_init(&vm_committed_as, 0, GFP_KERNEL);
3648        VM_BUG_ON(ret);
3649}
3650
3651/*
3652 * Initialise sysctl_user_reserve_kbytes.
3653 *
3654 * This is intended to prevent a user from starting a single memory hogging
3655 * process, such that they cannot recover (kill the hog) in OVERCOMMIT_NEVER
3656 * mode.
3657 *
3658 * The default value is min(3% of free memory, 128MB)
3659 * 128MB is enough to recover with sshd/login, bash, and top/kill.
3660 */
3661static int init_user_reserve(void)
3662{
3663        unsigned long free_kbytes;
3664
3665        free_kbytes = global_zone_page_state(NR_FREE_PAGES) << (PAGE_SHIFT - 10);
3666
3667        sysctl_user_reserve_kbytes = min(free_kbytes / 32, 1UL << 17);
3668        return 0;
3669}
3670subsys_initcall(init_user_reserve);
3671
3672/*
3673 * Initialise sysctl_admin_reserve_kbytes.
3674 *
3675 * The purpose of sysctl_admin_reserve_kbytes is to allow the sys admin
3676 * to log in and kill a memory hogging process.
3677 *
3678 * Systems with more than 256MB will reserve 8MB, enough to recover
3679 * with sshd, bash, and top in OVERCOMMIT_GUESS. Smaller systems will
3680 * only reserve 3% of free pages by default.
3681 */
3682static int init_admin_reserve(void)
3683{
3684        unsigned long free_kbytes;
3685
3686        free_kbytes = global_zone_page_state(NR_FREE_PAGES) << (PAGE_SHIFT - 10);
3687
3688        sysctl_admin_reserve_kbytes = min(free_kbytes / 32, 1UL << 13);
3689        return 0;
3690}
3691subsys_initcall(init_admin_reserve);
3692
3693/*
3694 * Reinititalise user and admin reserves if memory is added or removed.
3695 *
3696 * The default user reserve max is 128MB, and the default max for the
3697 * admin reserve is 8MB. These are usually, but not always, enough to
3698 * enable recovery from a memory hogging process using login/sshd, a shell,
3699 * and tools like top. It may make sense to increase or even disable the
3700 * reserve depending on the existence of swap or variations in the recovery
3701 * tools. So, the admin may have changed them.
3702 *
3703 * If memory is added and the reserves have been eliminated or increased above
3704 * the default max, then we'll trust the admin.
3705 *
3706 * If memory is removed and there isn't enough free memory, then we
3707 * need to reset the reserves.
3708 *
3709 * Otherwise keep the reserve set by the admin.
3710 */
3711static int reserve_mem_notifier(struct notifier_block *nb,
3712                             unsigned long action, void *data)
3713{
3714        unsigned long tmp, free_kbytes;
3715
3716        switch (action) {
3717        case MEM_ONLINE:
3718                /* Default max is 128MB. Leave alone if modified by operator. */
3719                tmp = sysctl_user_reserve_kbytes;
3720                if (0 < tmp && tmp < (1UL << 17))
3721                        init_user_reserve();
3722
3723                /* Default max is 8MB.  Leave alone if modified by operator. */
3724                tmp = sysctl_admin_reserve_kbytes;
3725                if (0 < tmp && tmp < (1UL << 13))
3726                        init_admin_reserve();
3727
3728                break;
3729        case MEM_OFFLINE:
3730                free_kbytes = global_zone_page_state(NR_FREE_PAGES) << (PAGE_SHIFT - 10);
3731
3732                if (sysctl_user_reserve_kbytes > free_kbytes) {
3733                        init_user_reserve();
3734                        pr_info("vm.user_reserve_kbytes reset to %lu\n",
3735                                sysctl_user_reserve_kbytes);
3736                }
3737
3738                if (sysctl_admin_reserve_kbytes > free_kbytes) {
3739                        init_admin_reserve();
3740                        pr_info("vm.admin_reserve_kbytes reset to %lu\n",
3741                                sysctl_admin_reserve_kbytes);
3742                }
3743                break;
3744        default:
3745                break;
3746        }
3747        return NOTIFY_OK;
3748}
3749
3750static struct notifier_block reserve_mem_nb = {
3751        .notifier_call = reserve_mem_notifier,
3752};
3753
3754static int __meminit init_reserve_notifier(void)
3755{
3756        if (register_hotmemory_notifier(&reserve_mem_nb))
3757                pr_err("Failed registering memory add/remove notifier for admin reserve\n");
3758
3759        return 0;
3760}
3761subsys_initcall(init_reserve_notifier);
3762