kernel/events/uprobes.c

   1 /*
   2  * User-space Probes (UProbes)
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17  *
  18  * Copyright (C) IBM Corporation, 2008-2012
  19  * Authors:
  20  *      Srikar Dronamraju
  21  *      Jim Keniston
  22  * Copyright (C) 2011-2012 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
  23  */
  24
  25 #include <linux/kernel.h>
  26 #include <linux/highmem.h>
  27 #include <linux/pagemap.h>      /* read_mapping_page */
  28 #include <linux/slab.h>
  29 #include <linux/sched.h>
  30 #include <linux/rmap.h>         /* anon_vma_prepare */
  31 #include <linux/mmu_notifier.h> /* set_pte_at_notify */
  32 #include <linux/swap.h>         /* try_to_free_swap */
  33
  34 #include <linux/uprobes.h>
  35
  36 static struct rb_root uprobes_tree = RB_ROOT;
  37
  38 static DEFINE_SPINLOCK(uprobes_treelock);       /* serialize rbtree access */
  39
  40 #define UPROBES_HASH_SZ 13
  41
  42 /* serialize (un)register */
  43 static struct mutex uprobes_mutex[UPROBES_HASH_SZ];
  44
  45 #define uprobes_hash(v)         (&uprobes_mutex[((unsigned long)(v)) % UPROBES_HASH_SZ])
  46
  47 /* serialize uprobe->pending_list */
  48 static struct mutex uprobes_mmap_mutex[UPROBES_HASH_SZ];
  49 #define uprobes_mmap_hash(v)    (&uprobes_mmap_mutex[((unsigned long)(v)) % UPROBES_HASH_SZ])
  50
  51 /*
  52  * uprobe_events allows us to skip the uprobe_mmap if there are no uprobe
  53  * events active at this time.  Probably a fine grained per inode count is
  54  * better?
  55  */
  56 static atomic_t uprobe_events = ATOMIC_INIT(0);
  57
  58 /*
  59  * Maintain a temporary per vma info that can be used to search if a vma
  60  * has already been handled. This structure is introduced since extending
  61  * vm_area_struct wasnt recommended.
  62  */
  63 struct vma_info {
  64         struct list_head        probe_list;
  65         struct mm_struct        *mm;
  66         loff_t                  vaddr;
  67 };
  68
  69 struct uprobe {
  70         struct rb_node          rb_node;        /* node in the rb tree */
  71         atomic_t                ref;
  72         struct rw_semaphore     consumer_rwsem;
  73         struct list_head        pending_list;
  74         struct uprobe_consumer  *consumers;
  75         struct inode            *inode;         /* Also hold a ref to inode */
  76         loff_t                  offset;
  77         int                     flags;
  78         struct arch_uprobe      arch;
  79 };
  80
  81 /*
  82  * valid_vma: Verify if the specified vma is an executable vma
  83  * Relax restrictions while unregistering: vm_flags might have
  84  * changed after breakpoint was inserted.
  85  *      - is_register: indicates if we are in register context.
  86  *      - Return 1 if the specified virtual address is in an
  87  *        executable vma.
  88  */
  89 static bool valid_vma(struct vm_area_struct *vma, bool is_register)
  90 {
  91         if (!vma->vm_file)
  92                 return false;
  93
  94         if (!is_register)
  95                 return true;
  96
  97         if ((vma->vm_flags & (VM_READ|VM_WRITE|VM_EXEC|VM_SHARED)) == (VM_READ|VM_EXEC))
  98                 return true;
  99
 100         return false;
 101 }
 102
 103 static loff_t vma_address(struct vm_area_struct *vma, loff_t offset)
 104 {
 105         loff_t vaddr;
 106
 107         vaddr = vma->vm_start + offset;
 108         vaddr -= vma->vm_pgoff << PAGE_SHIFT;
 109
 110         return vaddr;
 111 }
 112
 113 /**
 114  * __replace_page - replace page in vma by new page.
 115  * based on replace_page in mm/ksm.c
 116  *
 117  * @vma:      vma that holds the pte pointing to page
 118  * @page:     the cowed page we are replacing by kpage
 119  * @kpage:    the modified page we replace page by
 120  *
 121  * Returns 0 on success, -EFAULT on failure.
 122  */
 123 static int __replace_page(struct vm_area_struct *vma, struct page *page, struct page *kpage)
 124 {
 125         struct mm_struct *mm = vma->vm_mm;
 126         pgd_t *pgd;
 127         pud_t *pud;
 128         pmd_t *pmd;
 129         pte_t *ptep;
 130         spinlock_t *ptl;
 131         unsigned long addr;
 132         int err = -EFAULT;
 133
 134         addr = page_address_in_vma(page, vma);
 135         if (addr == -EFAULT)
 136                 goto out;
 137
 138         pgd = pgd_offset(mm, addr);
 139         if (!pgd_present(*pgd))
 140                 goto out;
 141
 142         pud = pud_offset(pgd, addr);
 143         if (!pud_present(*pud))
 144                 goto out;
 145
 146         pmd = pmd_offset(pud, addr);
 147         if (!pmd_present(*pmd))
 148                 goto out;
 149
 150         ptep = pte_offset_map_lock(mm, pmd, addr, &ptl);
 151         if (!ptep)
 152                 goto out;
 153
 154         get_page(kpage);
 155         page_add_new_anon_rmap(kpage, vma, addr);
 156
 157         flush_cache_page(vma, addr, pte_pfn(*ptep));
 158         ptep_clear_flush(vma, addr, ptep);
 159         set_pte_at_notify(mm, addr, ptep, mk_pte(kpage, vma->vm_page_prot));
 160
 161         page_remove_rmap(page);
 162         if (!page_mapped(page))
 163                 try_to_free_swap(page);
 164         put_page(page);
 165         pte_unmap_unlock(ptep, ptl);
 166         err = 0;
 167
 168 out:
 169         return err;
 170 }
 171
 172 /**
 173  * is_bkpt_insn - check if instruction is breakpoint instruction.
 174  * @insn: instruction to be checked.
 175  * Default implementation of is_bkpt_insn
 176  * Returns true if @insn is a breakpoint instruction.
 177  */
 178 bool __weak is_bkpt_insn(uprobe_opcode_t *insn)
 179 {
 180         return *insn == UPROBES_BKPT_INSN;
 181 }
 182
 183 /*
 184  * NOTE:
 185  * Expect the breakpoint instruction to be the smallest size instruction for
 186  * the architecture. If an arch has variable length instruction and the
 187  * breakpoint instruction is not of the smallest length instruction
 188  * supported by that architecture then we need to modify read_opcode /
 189  * write_opcode accordingly. This would never be a problem for archs that
 190  * have fixed length instructions.
 191  */
 192
 193 /*
 194  * write_opcode - write the opcode at a given virtual address.
 195  * @mm: the probed process address space.
 196  * @arch_uprobe: the breakpointing information.
 197  * @vaddr: the virtual address to store the opcode.
 198  * @opcode: opcode to be written at @vaddr.
 199  *
 200  * Called with mm->mmap_sem held (for read and with a reference to
 201  * mm).
 202  *
 203  * For mm @mm, write the opcode at @vaddr.
 204  * Return 0 (success) or a negative errno.
 205  */
 206 static int write_opcode(struct mm_struct *mm, struct arch_uprobe *auprobe,
 207                         unsigned long vaddr, uprobe_opcode_t opcode)
 208 {
 209         struct page *old_page, *new_page;
 210         struct address_space *mapping;
 211         void *vaddr_old, *vaddr_new;
 212         struct vm_area_struct *vma;
 213         struct uprobe *uprobe;
 214         loff_t addr;
 215         int ret;
 216
 217         /* Read the page with vaddr into memory */
 218         ret = get_user_pages(NULL, mm, vaddr, 1, 0, 0, &old_page, &vma);
 219         if (ret <= 0)
 220                 return ret;
 221
 222         ret = -EINVAL;
 223
 224         /*
 225          * We are interested in text pages only. Our pages of interest
 226          * should be mapped for read and execute only. We desist from
 227          * adding probes in write mapped pages since the breakpoints
 228          * might end up in the file copy.
 229          */
 230         if (!valid_vma(vma, is_bkpt_insn(&opcode)))
 231                 goto put_out;
 232
 233         uprobe = container_of(auprobe, struct uprobe, arch);
 234         mapping = uprobe->inode->i_mapping;
 235         if (mapping != vma->vm_file->f_mapping)
 236                 goto put_out;
 237
 238         addr = vma_address(vma, uprobe->offset);
 239         if (vaddr != (unsigned long)addr)
 240                 goto put_out;
 241
 242         ret = -ENOMEM;
 243         new_page = alloc_page_vma(GFP_HIGHUSER_MOVABLE, vma, vaddr);
 244         if (!new_page)
 245                 goto put_out;
 246
 247         __SetPageUptodate(new_page);
 248
 249         /*
 250          * lock page will serialize against do_wp_page()'s
 251          * PageAnon() handling
 252          */
 253         lock_page(old_page);
 254         /* copy the page now that we've got it stable */
 255         vaddr_old = kmap_atomic(old_page);
 256         vaddr_new = kmap_atomic(new_page);
 257
 258         memcpy(vaddr_new, vaddr_old, PAGE_SIZE);
 259
 260         /* poke the new insn in, ASSUMES we don't cross page boundary */
 261         vaddr &= ~PAGE_MASK;
 262         BUG_ON(vaddr + UPROBES_BKPT_INSN_SIZE > PAGE_SIZE);
 263         memcpy(vaddr_new + vaddr, &opcode, UPROBES_BKPT_INSN_SIZE);
 264
 265         kunmap_atomic(vaddr_new);
 266         kunmap_atomic(vaddr_old);
 267
 268         ret = anon_vma_prepare(vma);
 269         if (ret)
 270                 goto unlock_out;
 271
 272         lock_page(new_page);
 273         ret = __replace_page(vma, old_page, new_page);
 274         unlock_page(new_page);
 275
 276 unlock_out:
 277         unlock_page(old_page);
 278         page_cache_release(new_page);
 279
 280 put_out:
 281         put_page(old_page);
 282
 283         return ret;
 284 }
 285
 286 /**
 287  * read_opcode - read the opcode at a given virtual address.
 288  * @mm: the probed process address space.
 289  * @vaddr: the virtual address to read the opcode.
 290  * @opcode: location to store the read opcode.
 291  *
 292  * Called with mm->mmap_sem held (for read and with a reference to
 293  * mm.
 294  *
 295  * For mm @mm, read the opcode at @vaddr and store it in @opcode.
 296  * Return 0 (success) or a negative errno.
 297  */
 298 static int read_opcode(struct mm_struct *mm, unsigned long vaddr, uprobe_opcode_t *opcode)
 299 {
 300         struct page *page;
 301         void *vaddr_new;
 302         int ret;
 303
 304         ret = get_user_pages(NULL, mm, vaddr, 1, 0, 0, &page, NULL);
 305         if (ret <= 0)
 306                 return ret;
 307
 308         lock_page(page);
 309         vaddr_new = kmap_atomic(page);
 310         vaddr &= ~PAGE_MASK;
 311         memcpy(opcode, vaddr_new + vaddr, UPROBES_BKPT_INSN_SIZE);
 312         kunmap_atomic(vaddr_new);
 313         unlock_page(page);
 314
 315         put_page(page);
 316
 317         return 0;
 318 }
 319
 320 static int is_bkpt_at_addr(struct mm_struct *mm, unsigned long vaddr)
 321 {
 322         uprobe_opcode_t opcode;
 323         int result;
 324
 325         result = read_opcode(mm, vaddr, &opcode);
 326         if (result)
 327                 return result;
 328
 329         if (is_bkpt_insn(&opcode))
 330                 return 1;
 331
 332         return 0;
 333 }
 334
 335 /**
 336  * set_bkpt - store breakpoint at a given address.
 337  * @mm: the probed process address space.
 338  * @uprobe: the probepoint information.
 339  * @vaddr: the virtual address to insert the opcode.
 340  *
 341  * For mm @mm, store the breakpoint instruction at @vaddr.
 342  * Return 0 (success) or a negative errno.
 343  */
 344 int __weak set_bkpt(struct mm_struct *mm, struct arch_uprobe *auprobe, unsigned long vaddr)
 345 {
 346         int result;
 347
 348         result = is_bkpt_at_addr(mm, vaddr);
 349         if (result == 1)
 350                 return -EEXIST;
 351
 352         if (result)
 353                 return result;
 354
 355         return write_opcode(mm, auprobe, vaddr, UPROBES_BKPT_INSN);
 356 }
 357
 358 /**
 359  * set_orig_insn - Restore the original instruction.
 360  * @mm: the probed process address space.
 361  * @uprobe: the probepoint information.
 362  * @vaddr: the virtual address to insert the opcode.
 363  * @verify: if true, verify existance of breakpoint instruction.
 364  *
 365  * For mm @mm, restore the original opcode (opcode) at @vaddr.
 366  * Return 0 (success) or a negative errno.
 367  */
 368 int __weak
 369 set_orig_insn(struct mm_struct *mm, struct arch_uprobe *auprobe, unsigned long vaddr, bool verify)
 370 {
 371         if (verify) {
 372                 int result;
 373
 374                 result = is_bkpt_at_addr(mm, vaddr);
 375                 if (!result)
 376                         return -EINVAL;
 377
 378                 if (result != 1)
 379                         return result;
 380         }
 381         return write_opcode(mm, auprobe, vaddr, *(uprobe_opcode_t *)auprobe->insn);
 382 }
 383
 384 static int match_uprobe(struct uprobe *l, struct uprobe *r)
 385 {
 386         if (l->inode < r->inode)
 387                 return -1;
 388
 389         if (l->inode > r->inode)
 390                 return 1;
 391
 392         if (l->offset < r->offset)
 393                 return -1;
 394
 395         if (l->offset > r->offset)
 396                 return 1;
 397
 398         return 0;
 399 }
 400
 401 static struct uprobe *__find_uprobe(struct inode *inode, loff_t offset)
 402 {
 403         struct uprobe u = { .inode = inode, .offset = offset };
 404         struct rb_node *n = uprobes_tree.rb_node;
 405         struct uprobe *uprobe;
 406         int match;
 407
 408         while (n) {
 409                 uprobe = rb_entry(n, struct uprobe, rb_node);
 410                 match = match_uprobe(&u, uprobe);
 411                 if (!match) {
 412                         atomic_inc(&uprobe->ref);
 413                         return uprobe;
 414                 }
 415
 416                 if (match < 0)
 417                         n = n->rb_left;
 418                 else
 419                         n = n->rb_right;
 420         }
 421         return NULL;
 422 }
 423
 424 /*
 425  * Find a uprobe corresponding to a given inode:offset
 426  * Acquires uprobes_treelock
 427  */
 428 static struct uprobe *find_uprobe(struct inode *inode, loff_t offset)
 429 {
 430         struct uprobe *uprobe;
 431         unsigned long flags;
 432
 433         spin_lock_irqsave(&uprobes_treelock, flags);
 434         uprobe = __find_uprobe(inode, offset);
 435         spin_unlock_irqrestore(&uprobes_treelock, flags);
 436
 437         return uprobe;
 438 }
 439
 440 static struct uprobe *__insert_uprobe(struct uprobe *uprobe)
 441 {
 442         struct rb_node **p = &uprobes_tree.rb_node;
 443         struct rb_node *parent = NULL;
 444         struct uprobe *u;
 445         int match;
 446
 447         while (*p) {
 448                 parent = *p;
 449                 u = rb_entry(parent, struct uprobe, rb_node);
 450                 match = match_uprobe(uprobe, u);
 451                 if (!match) {
 452                         atomic_inc(&u->ref);
 453                         return u;
 454                 }
 455
 456                 if (match < 0)
 457                         p = &parent->rb_left;
 458                 else
 459                         p = &parent->rb_right;
 460
 461         }
 462
 463         u = NULL;
 464         rb_link_node(&uprobe->rb_node, parent, p);
 465         rb_insert_color(&uprobe->rb_node, &uprobes_tree);
 466         /* get access + creation ref */
 467         atomic_set(&uprobe->ref, 2);
 468
 469         return u;
 470 }
 471
 472 /*
 473  * Acquire uprobes_treelock.
 474  * Matching uprobe already exists in rbtree;
 475  *      increment (access refcount) and return the matching uprobe.
 476  *
 477  * No matching uprobe; insert the uprobe in rb_tree;
 478  *      get a double refcount (access + creation) and return NULL.
 479  */
 480 static struct uprobe *insert_uprobe(struct uprobe *uprobe)
 481 {
 482         unsigned long flags;
 483         struct uprobe *u;
 484
 485         spin_lock_irqsave(&uprobes_treelock, flags);
 486         u = __insert_uprobe(uprobe);
 487         spin_unlock_irqrestore(&uprobes_treelock, flags);
 488
 489         return u;
 490 }
 491
 492 static void put_uprobe(struct uprobe *uprobe)
 493 {
 494         if (atomic_dec_and_test(&uprobe->ref))
 495                 kfree(uprobe);
 496 }
 497
 498 static struct uprobe *alloc_uprobe(struct inode *inode, loff_t offset)
 499 {
 500         struct uprobe *uprobe, *cur_uprobe;
 501
 502         uprobe = kzalloc(sizeof(struct uprobe), GFP_KERNEL);
 503         if (!uprobe)
 504                 return NULL;
 505
 506         uprobe->inode = igrab(inode);
 507         uprobe->offset = offset;
 508         init_rwsem(&uprobe->consumer_rwsem);
 509         INIT_LIST_HEAD(&uprobe->pending_list);
 510
 511         /* add to uprobes_tree, sorted on inode:offset */
 512         cur_uprobe = insert_uprobe(uprobe);
 513
 514         /* a uprobe exists for this inode:offset combination */
 515         if (cur_uprobe) {
 516                 kfree(uprobe);
 517                 uprobe = cur_uprobe;
 518                 iput(inode);
 519         } else {
 520                 atomic_inc(&uprobe_events);
 521         }
 522
 523         return uprobe;
 524 }
 525
 526 /* Returns the previous consumer */
 527 static struct uprobe_consumer *
 528 consumer_add(struct uprobe *uprobe, struct uprobe_consumer *consumer)
 529 {
 530         down_write(&uprobe->consumer_rwsem);
 531         consumer->next = uprobe->consumers;
 532         uprobe->consumers = consumer;
 533         up_write(&uprobe->consumer_rwsem);
 534
 535         return consumer->next;
 536 }
 537
 538 /*
 539  * For uprobe @uprobe, delete the consumer @consumer.
 540  * Return true if the @consumer is deleted successfully
 541  * or return false.
 542  */
 543 static bool consumer_del(struct uprobe *uprobe, struct uprobe_consumer *consumer)
 544 {
 545         struct uprobe_consumer **con;
 546         bool ret = false;
 547
 548         down_write(&uprobe->consumer_rwsem);
 549         for (con = &uprobe->consumers; *con; con = &(*con)->next) {
 550                 if (*con == consumer) {
 551                         *con = consumer->next;
 552                         ret = true;
 553                         break;
 554                 }
 555         }
 556         up_write(&uprobe->consumer_rwsem);
 557
 558         return ret;
 559 }
 560
 561 static int __copy_insn(struct address_space *mapping,
 562                         struct vm_area_struct *vma, char *insn,
 563                         unsigned long nbytes, unsigned long offset)
 564 {
 565         struct file *filp = vma->vm_file;
 566         struct page *page;
 567         void *vaddr;
 568         unsigned long off1;
 569         unsigned long idx;
 570
 571         if (!filp)
 572                 return -EINVAL;
 573
 574         idx = (unsigned long)(offset >> PAGE_CACHE_SHIFT);
 575         off1 = offset &= ~PAGE_MASK;
 576
 577         /*
 578          * Ensure that the page that has the original instruction is
 579          * populated and in page-cache.
 580          */
 581         page = read_mapping_page(mapping, idx, filp);
 582         if (IS_ERR(page))
 583                 return PTR_ERR(page);
 584
 585         vaddr = kmap_atomic(page);
 586         memcpy(insn, vaddr + off1, nbytes);
 587         kunmap_atomic(vaddr);
 588         page_cache_release(page);
 589
 590         return 0;
 591 }
 592
 593 static int copy_insn(struct uprobe *uprobe, struct vm_area_struct *vma, unsigned long addr)
 594 {
 595         struct address_space *mapping;
 596         unsigned long nbytes;
 597         int bytes;
 598
 599         addr &= ~PAGE_MASK;
 600         nbytes = PAGE_SIZE - addr;
 601         mapping = uprobe->inode->i_mapping;
 602
 603         /* Instruction at end of binary; copy only available bytes */
 604         if (uprobe->offset + MAX_UINSN_BYTES > uprobe->inode->i_size)
 605                 bytes = uprobe->inode->i_size - uprobe->offset;
 606         else
 607                 bytes = MAX_UINSN_BYTES;
 608
 609         /* Instruction at the page-boundary; copy bytes in second page */
 610         if (nbytes < bytes) {
 611                 if (__copy_insn(mapping, vma, uprobe->arch.insn + nbytes,
 612                                 bytes - nbytes, uprobe->offset + nbytes))
 613                         return -ENOMEM;
 614
 615                 bytes = nbytes;
 616         }
 617         return __copy_insn(mapping, vma, uprobe->arch.insn, bytes, uprobe->offset);
 618 }
 619
 620 static int install_breakpoint(struct mm_struct *mm, struct uprobe *uprobe,
 621                                 struct vm_area_struct *vma, loff_t vaddr)
 622 {
 623         unsigned long addr;
 624         int ret;
 625
 626         /*
 627          * If probe is being deleted, unregister thread could be done with
 628          * the vma-rmap-walk through. Adding a probe now can be fatal since
 629          * nobody will be able to cleanup. Also we could be from fork or
 630          * mremap path, where the probe might have already been inserted.
 631          * Hence behave as if probe already existed.
 632          */
 633         if (!uprobe->consumers)
 634                 return -EEXIST;
 635
 636         addr = (unsigned long)vaddr;
 637
 638         if (!(uprobe->flags & UPROBES_COPY_INSN)) {
 639                 ret = copy_insn(uprobe, vma, addr);
 640                 if (ret)
 641                         return ret;
 642
 643                 if (is_bkpt_insn((uprobe_opcode_t *)uprobe->arch.insn))
 644                         return -EEXIST;
 645
 646                 ret = arch_uprobes_analyze_insn(mm, &uprobe->arch);
 647                 if (ret)
 648                         return ret;
 649
 650                 uprobe->flags |= UPROBES_COPY_INSN;
 651         }
 652         ret = set_bkpt(mm, &uprobe->arch, addr);
 653
 654         return ret;
 655 }
 656
 657 static void remove_breakpoint(struct mm_struct *mm, struct uprobe *uprobe, loff_t vaddr)
 658 {
 659         set_orig_insn(mm, &uprobe->arch, (unsigned long)vaddr, true);
 660 }
 661
 662 static void delete_uprobe(struct uprobe *uprobe)
 663 {
 664         unsigned long flags;
 665
 666         spin_lock_irqsave(&uprobes_treelock, flags);
 667         rb_erase(&uprobe->rb_node, &uprobes_tree);
 668         spin_unlock_irqrestore(&uprobes_treelock, flags);
 669         iput(uprobe->inode);
 670         put_uprobe(uprobe);
 671         atomic_dec(&uprobe_events);
 672 }
 673
 674 static struct vma_info *__find_next_vma_info(struct list_head *head,
 675                         loff_t offset, struct address_space *mapping,
 676                         struct vma_info *vi, bool is_register)
 677 {
 678         struct prio_tree_iter iter;
 679         struct vm_area_struct *vma;
 680         struct vma_info *tmpvi;
 681         unsigned long pgoff;
 682         int existing_vma;
 683         loff_t vaddr;
 684
 685         pgoff = offset >> PAGE_SHIFT;
 686
 687         vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
 688                 if (!valid_vma(vma, is_register))
 689                         continue;
 690
 691                 existing_vma = 0;
 692                 vaddr = vma_address(vma, offset);
 693
 694                 list_for_each_entry(tmpvi, head, probe_list) {
 695                         if (tmpvi->mm == vma->vm_mm && tmpvi->vaddr == vaddr) {
 696                                 existing_vma = 1;
 697                                 break;
 698                         }
 699                 }
 700
 701                 /*
 702                  * Another vma needs a probe to be installed. However skip
 703                  * installing the probe if the vma is about to be unlinked.
 704                  */
 705                 if (!existing_vma && atomic_inc_not_zero(&vma->vm_mm->mm_users)) {
 706                         vi->mm = vma->vm_mm;
 707                         vi->vaddr = vaddr;
 708                         list_add(&vi->probe_list, head);
 709
 710                         return vi;
 711                 }
 712         }
 713
 714         return NULL;
 715 }
 716
 717 /*
 718  * Iterate in the rmap prio tree  and find a vma where a probe has not
 719  * yet been inserted.
 720  */
 721 static struct vma_info *
 722 find_next_vma_info(struct list_head *head, loff_t offset, struct address_space *mapping,
 723                    bool is_register)
 724 {
 725         struct vma_info *vi, *retvi;
 726
 727         vi = kzalloc(sizeof(struct vma_info), GFP_KERNEL);
 728         if (!vi)
 729                 return ERR_PTR(-ENOMEM);
 730
 731         mutex_lock(&mapping->i_mmap_mutex);
 732         retvi = __find_next_vma_info(head, offset, mapping, vi, is_register);
 733         mutex_unlock(&mapping->i_mmap_mutex);
 734
 735         if (!retvi)
 736                 kfree(vi);
 737
 738         return retvi;
 739 }
 740
 741 static int register_for_each_vma(struct uprobe *uprobe, bool is_register)
 742 {
 743         struct list_head try_list;
 744         struct vm_area_struct *vma;
 745         struct address_space *mapping;
 746         struct vma_info *vi, *tmpvi;
 747         struct mm_struct *mm;
 748         loff_t vaddr;
 749         int ret;
 750
 751         mapping = uprobe->inode->i_mapping;
 752         INIT_LIST_HEAD(&try_list);
 753
 754         ret = 0;
 755
 756         for (;;) {
 757                 vi = find_next_vma_info(&try_list, uprobe->offset, mapping, is_register);
 758                 if (!vi)
 759                         break;
 760
 761                 if (IS_ERR(vi)) {
 762                         ret = PTR_ERR(vi);
 763                         break;
 764                 }
 765
 766                 mm = vi->mm;
 767                 down_read(&mm->mmap_sem);
 768                 vma = find_vma(mm, (unsigned long)vi->vaddr);
 769                 if (!vma || !valid_vma(vma, is_register)) {
 770                         list_del(&vi->probe_list);
 771                         kfree(vi);
 772                         up_read(&mm->mmap_sem);
 773                         mmput(mm);
 774                         continue;
 775                 }
 776                 vaddr = vma_address(vma, uprobe->offset);
 777                 if (vma->vm_file->f_mapping->host != uprobe->inode ||
 778                                                 vaddr != vi->vaddr) {
 779                         list_del(&vi->probe_list);
 780                         kfree(vi);
 781                         up_read(&mm->mmap_sem);
 782                         mmput(mm);
 783                         continue;
 784                 }
 785
 786                 if (is_register)
 787                         ret = install_breakpoint(mm, uprobe, vma, vi->vaddr);
 788                 else
 789                         remove_breakpoint(mm, uprobe, vi->vaddr);
 790
 791                 up_read(&mm->mmap_sem);
 792                 mmput(mm);
 793                 if (is_register) {
 794                         if (ret && ret == -EEXIST)
 795                                 ret = 0;
 796                         if (ret)
 797                                 break;
 798                 }
 799         }
 800
 801         list_for_each_entry_safe(vi, tmpvi, &try_list, probe_list) {
 802                 list_del(&vi->probe_list);
 803                 kfree(vi);
 804         }
 805
 806         return ret;
 807 }
 808
 809 static int __uprobe_register(struct uprobe *uprobe)
 810 {
 811         return register_for_each_vma(uprobe, true);
 812 }
 813
 814 static void __uprobe_unregister(struct uprobe *uprobe)
 815 {
 816         if (!register_for_each_vma(uprobe, false))
 817                 delete_uprobe(uprobe);
 818
 819         /* TODO : cant unregister? schedule a worker thread */
 820 }
 821
 822 /*
 823  * uprobe_register - register a probe
 824  * @inode: the file in which the probe has to be placed.
 825  * @offset: offset from the start of the file.
 826  * @consumer: information on howto handle the probe..
 827  *
 828  * Apart from the access refcount, uprobe_register() takes a creation
 829  * refcount (thro alloc_uprobe) if and only if this @uprobe is getting
 830  * inserted into the rbtree (i.e first consumer for a @inode:@offset
 831  * tuple).  Creation refcount stops uprobe_unregister from freeing the
 832  * @uprobe even before the register operation is complete. Creation
 833  * refcount is released when the last @consumer for the @uprobe
 834  * unregisters.
 835  *
 836  * Return errno if it cannot successully install probes
 837  * else return 0 (success)
 838  */
 839 int uprobe_register(struct inode *inode, loff_t offset, struct uprobe_consumer *consumer)
 840 {
 841         struct uprobe *uprobe;
 842         int ret;
 843
 844         if (!inode || !consumer || consumer->next)
 845                 return -EINVAL;
 846
 847         if (offset > i_size_read(inode))
 848                 return -EINVAL;
 849
 850         ret = 0;
 851         mutex_lock(uprobes_hash(inode));
 852         uprobe = alloc_uprobe(inode, offset);
 853
 854         if (uprobe && !consumer_add(uprobe, consumer)) {
 855                 ret = __uprobe_register(uprobe);
 856                 if (ret) {
 857                         uprobe->consumers = NULL;
 858                         __uprobe_unregister(uprobe);
 859                 } else {
 860                         uprobe->flags |= UPROBES_RUN_HANDLER;
 861                 }
 862         }
 863
 864         mutex_unlock(uprobes_hash(inode));
 865         put_uprobe(uprobe);
 866
 867         return ret;
 868 }
 869
 870 /*
 871  * uprobe_unregister - unregister a already registered probe.
 872  * @inode: the file in which the probe has to be removed.
 873  * @offset: offset from the start of the file.
 874  * @consumer: identify which probe if multiple probes are colocated.
 875  */
 876 void uprobe_unregister(struct inode *inode, loff_t offset, struct uprobe_consumer *consumer)
 877 {
 878         struct uprobe *uprobe;
 879
 880         if (!inode || !consumer)
 881                 return;
 882
 883         uprobe = find_uprobe(inode, offset);
 884         if (!uprobe)
 885                 return;
 886
 887         mutex_lock(uprobes_hash(inode));
 888
 889         if (consumer_del(uprobe, consumer)) {
 890                 if (!uprobe->consumers) {
 891                         __uprobe_unregister(uprobe);
 892                         uprobe->flags &= ~UPROBES_RUN_HANDLER;
 893                 }
 894         }
 895
 896         mutex_unlock(uprobes_hash(inode));
 897         if (uprobe)
 898                 put_uprobe(uprobe);
 899 }
 900
 901 /*
 902  * Of all the nodes that correspond to the given inode, return the node
 903  * with the least offset.
 904  */
 905 static struct rb_node *find_least_offset_node(struct inode *inode)
 906 {
 907         struct uprobe u = { .inode = inode, .offset = 0};
 908         struct rb_node *n = uprobes_tree.rb_node;
 909         struct rb_node *close_node = NULL;
 910         struct uprobe *uprobe;
 911         int match;
 912
 913         while (n) {
 914                 uprobe = rb_entry(n, struct uprobe, rb_node);
 915                 match = match_uprobe(&u, uprobe);
 916
 917                 if (uprobe->inode == inode)
 918                         close_node = n;
 919
 920                 if (!match)
 921                         return close_node;
 922
 923                 if (match < 0)
 924                         n = n->rb_left;
 925                 else
 926                         n = n->rb_right;
 927         }
 928
 929         return close_node;
 930 }
 931
 932 /*
 933  * For a given inode, build a list of probes that need to be inserted.
 934  */
 935 static void build_probe_list(struct inode *inode, struct list_head *head)
 936 {
 937         struct uprobe *uprobe;
 938         unsigned long flags;
 939         struct rb_node *n;
 940
 941         spin_lock_irqsave(&uprobes_treelock, flags);
 942
 943         n = find_least_offset_node(inode);
 944
 945         for (; n; n = rb_next(n)) {
 946                 uprobe = rb_entry(n, struct uprobe, rb_node);
 947                 if (uprobe->inode != inode)
 948                         break;
 949
 950                 list_add(&uprobe->pending_list, head);
 951                 atomic_inc(&uprobe->ref);
 952         }
 953
 954         spin_unlock_irqrestore(&uprobes_treelock, flags);
 955 }
 956
 957 /*
 958  * Called from mmap_region.
 959  * called with mm->mmap_sem acquired.
 960  *
 961  * Return -ve no if we fail to insert probes and we cannot
 962  * bail-out.
 963  * Return 0 otherwise. i.e:
 964  *
 965  *      - successful insertion of probes
 966  *      - (or) no possible probes to be inserted.
 967  *      - (or) insertion of probes failed but we can bail-out.
 968  */
 969 int uprobe_mmap(struct vm_area_struct *vma)
 970 {
 971         struct list_head tmp_list;
 972         struct uprobe *uprobe, *u;
 973         struct inode *inode;
 974         int ret;
 975
 976         if (!atomic_read(&uprobe_events) || !valid_vma(vma, true))
 977                 return 0;
 978
 979         inode = vma->vm_file->f_mapping->host;
 980         if (!inode)
 981                 return 0;
 982
 983         INIT_LIST_HEAD(&tmp_list);
 984         mutex_lock(uprobes_mmap_hash(inode));
 985         build_probe_list(inode, &tmp_list);
 986
 987         ret = 0;
 988
 989         list_for_each_entry_safe(uprobe, u, &tmp_list, pending_list) {
 990                 loff_t vaddr;
 991
 992                 list_del(&uprobe->pending_list);
 993                 if (!ret) {
 994                         vaddr = vma_address(vma, uprobe->offset);
 995                         if (vaddr >= vma->vm_start && vaddr < vma->vm_end) {
 996                                 ret = install_breakpoint(vma->vm_mm, uprobe, vma, vaddr);
 997                                 /* Ignore double add: */
 998                                 if (ret == -EEXIST)
 999                                         ret = 0;
1000                         }
1001                 }
1002                 put_uprobe(uprobe);
1003         }
1004
1005         mutex_unlock(uprobes_mmap_hash(inode));
1006
1007         return ret;
1008 }
1009
1010 static int __init init_uprobes(void)
1011 {
1012         int i;
1013
1014         for (i = 0; i < UPROBES_HASH_SZ; i++) {
1015                 mutex_init(&uprobes_mutex[i]);
1016                 mutex_init(&uprobes_mmap_mutex[i]);
1017         }
1018         return 0;
1019 }
1020
1021 static void __exit exit_uprobes(void)
1022 {
1023 }
1024
1025 module_init(init_uprobes);
1026 module_exit(exit_uprobes);