// SPDX-License-Identifier: GPL-2.0-or-later

  /*
   *  Kernel Probes (KProbes)
   *  kernel/kprobes.c
   *

   * Copyright (C) IBM Corporation, 2002, 2004
   *
   * 2002-Oct	Created by Vamsi Krishna S <vamsi_krishna@in.ibm.com> Kernel
   *		Probes initial implementation (includes suggestions from
   *		Rusty Russell).
   * 2004-Aug	Updated by Prasanna S Panchamukhi <prasanna@in.ibm.com> with
   *		hlists and exceptions notifier as suggested by Andi Kleen.
   * 2004-July	Suparna Bhattacharya <suparna@in.ibm.com> added jumper probes
   *		interface to access function arguments.
   * 2004-Sep	Prasanna S Panchamukhi <prasanna@in.ibm.com> Changed Kprobes
   *		exceptions notifier to be first on the priority list.

   * 2005-May	Hien Nguyen <hien@us.ibm.com>, Jim Keniston
   *		<jkenisto@us.ibm.com> and Prasanna S Panchamukhi
   *		<prasanna@in.ibm.com> added function-return probes.

   */
  #include <linux/kprobes.h>

  #include <linux/hash.h>
  #include <linux/init.h>

  #include <linux/slab.h>

  #include <linux/stddef.h>

  #include <linux/export.h>

  #include <linux/moduleloader.h>

  #include <linux/kallsyms.h>

  #include <linux/freezer.h>

  #include <linux/seq_file.h>
  #include <linux/debugfs.h>

  #include <linux/sysctl.h>

  #include <linux/kdebug.h>

  #include <linux/memory.h>

  #include <linux/ftrace.h>

  #include <linux/cpu.h>

  #include <linux/jump_label.h>

  #include <linux/perf_event.h>

  #include <linux/static_call.h>

  #include <asm/sections.h>

  #include <asm/cacheflush.h>
  #include <asm/errno.h>

  #include <linux/uaccess.h>

  
  #define KPROBE_HASH_BITS 6
  #define KPROBE_TABLE_SIZE (1 << KPROBE_HASH_BITS)

  static int kprobes_initialized;

  /* kprobe_table can be accessed by
   * - Normal hlist traversal and RCU add/del under kprobe_mutex is held.
   * Or
   * - RCU hlist traversal under disabling preempt (breakpoint handlers)
   */

  static struct hlist_head kprobe_table[KPROBE_TABLE_SIZE];

  static struct hlist_head kretprobe_inst_table[KPROBE_TABLE_SIZE];

  /* NOTE: change this value only with kprobe_mutex held */

  static bool kprobes_all_disarmed;

  /* This protects kprobe_table and optimizing_list */
  static DEFINE_MUTEX(kprobe_mutex);

  static DEFINE_PER_CPU(struct kprobe *, kprobe_instance) = NULL;

  static struct {

  	raw_spinlock_t lock ____cacheline_aligned_in_smp;

  } kretprobe_table_locks[KPROBE_TABLE_SIZE];

  kprobe_opcode_t * __weak kprobe_lookup_name(const char *name,
  					unsigned int __unused)

  {
  	return ((kprobe_opcode_t *)(kallsyms_lookup_name(name)));
  }

  static raw_spinlock_t *kretprobe_table_lock_ptr(unsigned long hash)

  {
  	return &(kretprobe_table_locks[hash].lock);
  }

  /* Blacklist -- list of struct kprobe_blacklist_entry */
  static LIST_HEAD(kprobe_blacklist);

  #ifdef __ARCH_WANT_KPROBES_INSN_SLOT

  /*
   * kprobe->ainsn.insn points to the copy of the instruction to be
   * single-stepped. x86_64, POWER4 and above have no-exec support and
   * stepping on the instruction on a vmalloced/kmalloced/data page
   * is a recipe for disaster
   */

  struct kprobe_insn_page {

  	struct list_head list;

  	kprobe_opcode_t *insns;		/* Page of instruction slots */

  	struct kprobe_insn_cache *cache;

  	int nused;

  	int ngarbage;

  	char slot_used[];

  };

  #define KPROBE_INSN_PAGE_SIZE(slots)			\
  	(offsetof(struct kprobe_insn_page, slot_used) +	\
  	 (sizeof(char) * (slots)))

  static int slots_per_page(struct kprobe_insn_cache *c)
  {
  	return PAGE_SIZE/(c->insn_size * sizeof(kprobe_opcode_t));
  }

  enum kprobe_slot_state {
  	SLOT_CLEAN = 0,
  	SLOT_DIRTY = 1,
  	SLOT_USED = 2,
  };

  void __weak *alloc_insn_page(void)

  {
  	return module_alloc(PAGE_SIZE);
  }

  void __weak free_insn_page(void *page)

  {

  	module_memfree(page);

  }

  struct kprobe_insn_cache kprobe_insn_slots = {
  	.mutex = __MUTEX_INITIALIZER(kprobe_insn_slots.mutex),

  	.alloc = alloc_insn_page,
  	.free = free_insn_page,

  	.sym = KPROBE_INSN_PAGE_SYM,

  	.pages = LIST_HEAD_INIT(kprobe_insn_slots.pages),
  	.insn_size = MAX_INSN_SIZE,
  	.nr_garbage = 0,
  };

  static int collect_garbage_slots(struct kprobe_insn_cache *c);

  /**

   * __get_insn_slot() - Find a slot on an executable page for an instruction.

   * We allocate an executable page if there's no room on existing ones.
   */

  kprobe_opcode_t *__get_insn_slot(struct kprobe_insn_cache *c)

  {
  	struct kprobe_insn_page *kip;

  	kprobe_opcode_t *slot = NULL;

  	/* Since the slot array is not protected by rcu, we need a mutex */

  	mutex_lock(&c->mutex);

   retry:

  	rcu_read_lock();
  	list_for_each_entry_rcu(kip, &c->pages, list) {

  		if (kip->nused < slots_per_page(c)) {

  			int i;

  			for (i = 0; i < slots_per_page(c); i++) {

  				if (kip->slot_used[i] == SLOT_CLEAN) {
  					kip->slot_used[i] = SLOT_USED;

  					kip->nused++;

  					slot = kip->insns + (i * c->insn_size);

  					rcu_read_unlock();

  					goto out;

  				}
  			}

  			/* kip->nused is broken. Fix it. */
  			kip->nused = slots_per_page(c);
  			WARN_ON(1);

  		}
  	}

  	rcu_read_unlock();

  	/* If there are any garbage slots, collect it and try again. */

  	if (c->nr_garbage && collect_garbage_slots(c) == 0)

  		goto retry;

  
  	/* All out of space.  Need to allocate a new page. */
  	kip = kmalloc(KPROBE_INSN_PAGE_SIZE(slots_per_page(c)), GFP_KERNEL);

  	if (!kip)

  		goto out;

  
  	/*
  	 * Use module_alloc so this page is within +/- 2GB of where the
  	 * kernel image and loaded module images reside. This is required
  	 * so x86_64 can correctly handle the %rip-relative fixups.
  	 */

  	kip->insns = c->alloc();

  	if (!kip->insns) {
  		kfree(kip);

  		goto out;

  	}

  	INIT_LIST_HEAD(&kip->list);

  	memset(kip->slot_used, SLOT_CLEAN, slots_per_page(c));

  	kip->slot_used[0] = SLOT_USED;

  	kip->nused = 1;

  	kip->ngarbage = 0;

  	kip->cache = c;

  	list_add_rcu(&kip->list, &c->pages);

  	slot = kip->insns;

  
  	/* Record the perf ksymbol register event after adding the page */
  	perf_event_ksymbol(PERF_RECORD_KSYMBOL_TYPE_OOL, (unsigned long)kip->insns,
  			   PAGE_SIZE, false, c->sym);

  out:
  	mutex_unlock(&c->mutex);
  	return slot;

  }

  /* Return 1 if all garbages are collected, otherwise 0. */

  static int collect_one_slot(struct kprobe_insn_page *kip, int idx)

  {

  	kip->slot_used[idx] = SLOT_CLEAN;

  	kip->nused--;
  	if (kip->nused == 0) {
  		/*
  		 * Page is no longer in use.  Free it unless
  		 * it's the last one.  We keep the last one
  		 * so as not to have to set it up again the
  		 * next time somebody inserts a probe.
  		 */

  		if (!list_is_singular(&kip->list)) {

  			/*
  			 * Record perf ksymbol unregister event before removing
  			 * the page.
  			 */
  			perf_event_ksymbol(PERF_RECORD_KSYMBOL_TYPE_OOL,
  					   (unsigned long)kip->insns, PAGE_SIZE, true,
  					   kip->cache->sym);

  			list_del_rcu(&kip->list);
  			synchronize_rcu();

  			kip->cache->free(kip->insns);

  			kfree(kip);
  		}
  		return 1;
  	}
  	return 0;
  }

  static int collect_garbage_slots(struct kprobe_insn_cache *c)

  {

  	struct kprobe_insn_page *kip, *next;

  	/* Ensure no-one is interrupted on the garbages */

  	synchronize_rcu();

  	list_for_each_entry_safe(kip, next, &c->pages, list) {

  		int i;

  		if (kip->ngarbage == 0)
  			continue;
  		kip->ngarbage = 0;	/* we will collect all garbages */

  		for (i = 0; i < slots_per_page(c); i++) {

  			if (kip->slot_used[i] == SLOT_DIRTY && collect_one_slot(kip, i))

  				break;
  		}
  	}

  	c->nr_garbage = 0;

  	return 0;
  }

  void __free_insn_slot(struct kprobe_insn_cache *c,
  		      kprobe_opcode_t *slot, int dirty)

  {
  	struct kprobe_insn_page *kip;

  	long idx;

  	mutex_lock(&c->mutex);

  	rcu_read_lock();
  	list_for_each_entry_rcu(kip, &c->pages, list) {
  		idx = ((long)slot - (long)kip->insns) /
  			(c->insn_size * sizeof(kprobe_opcode_t));
  		if (idx >= 0 && idx < slots_per_page(c))

  			goto out;

  	}

  	/* Could not find this slot. */

  	WARN_ON(1);

  	kip = NULL;

  out:

  	rcu_read_unlock();
  	/* Mark and sweep: this may sleep */
  	if (kip) {
  		/* Check double free */
  		WARN_ON(kip->slot_used[idx] != SLOT_USED);
  		if (dirty) {
  			kip->slot_used[idx] = SLOT_DIRTY;
  			kip->ngarbage++;
  			if (++c->nr_garbage > slots_per_page(c))
  				collect_garbage_slots(c);
  		} else {
  			collect_one_slot(kip, idx);
  		}
  	}

  	mutex_unlock(&c->mutex);

  }

  /*
   * Check given address is on the page of kprobe instruction slots.
   * This will be used for checking whether the address on a stack
   * is on a text area or not.
   */
  bool __is_insn_slot_addr(struct kprobe_insn_cache *c, unsigned long addr)
  {
  	struct kprobe_insn_page *kip;
  	bool ret = false;
  
  	rcu_read_lock();
  	list_for_each_entry_rcu(kip, &c->pages, list) {
  		if (addr >= (unsigned long)kip->insns &&
  		    addr < (unsigned long)kip->insns + PAGE_SIZE) {
  			ret = true;
  			break;
  		}
  	}
  	rcu_read_unlock();
  
  	return ret;
  }

  int kprobe_cache_get_kallsym(struct kprobe_insn_cache *c, unsigned int *symnum,
  			     unsigned long *value, char *type, char *sym)
  {
  	struct kprobe_insn_page *kip;
  	int ret = -ERANGE;
  
  	rcu_read_lock();
  	list_for_each_entry_rcu(kip, &c->pages, list) {
  		if ((*symnum)--)
  			continue;
  		strlcpy(sym, c->sym, KSYM_NAME_LEN);
  		*type = 't';
  		*value = (unsigned long)kip->insns;
  		ret = 0;
  		break;
  	}
  	rcu_read_unlock();
  
  	return ret;
  }

  #ifdef CONFIG_OPTPROBES
  /* For optimized_kprobe buffer */

  struct kprobe_insn_cache kprobe_optinsn_slots = {
  	.mutex = __MUTEX_INITIALIZER(kprobe_optinsn_slots.mutex),

  	.alloc = alloc_insn_page,
  	.free = free_insn_page,

  	.sym = KPROBE_OPTINSN_PAGE_SYM,

  	.pages = LIST_HEAD_INIT(kprobe_optinsn_slots.pages),
  	/* .insn_size is initialized later */
  	.nr_garbage = 0,
  };

  #endif

  #endif

  /* We have preemption disabled.. so it is safe to use __ versions */
  static inline void set_kprobe_instance(struct kprobe *kp)
  {

  	__this_cpu_write(kprobe_instance, kp);

  }
  
  static inline void reset_kprobe_instance(void)
  {

  	__this_cpu_write(kprobe_instance, NULL);

  }

  /*
   * This routine is called either:

   * 	- under the kprobe_mutex - during kprobe_[un]register()

   * 				OR

   * 	- with preemption disabled - from arch/xxx/kernel/kprobes.c

   */

  struct kprobe *get_kprobe(void *addr)

  {
  	struct hlist_head *head;

  	struct kprobe *p;

  
  	head = &kprobe_table[hash_ptr(addr, KPROBE_HASH_BITS)];

  	hlist_for_each_entry_rcu(p, head, hlist,
  				 lockdep_is_held(&kprobe_mutex)) {

  		if (p->addr == addr)
  			return p;
  	}

  	return NULL;
  }

  NOKPROBE_SYMBOL(get_kprobe);

  static int aggr_pre_handler(struct kprobe *p, struct pt_regs *regs);

  
  /* Return true if the kprobe is an aggregator */
  static inline int kprobe_aggrprobe(struct kprobe *p)
  {
  	return p->pre_handler == aggr_pre_handler;
  }

  /* Return true(!0) if the kprobe is unused */
  static inline int kprobe_unused(struct kprobe *p)
  {
  	return kprobe_aggrprobe(p) && kprobe_disabled(p) &&
  	       list_empty(&p->list);
  }

  /*
   * Keep all fields in the kprobe consistent
   */

  static inline void copy_kprobe(struct kprobe *ap, struct kprobe *p)

  {

  	memcpy(&p->opcode, &ap->opcode, sizeof(kprobe_opcode_t));
  	memcpy(&p->ainsn, &ap->ainsn, sizeof(struct arch_specific_insn));

  }
  
  #ifdef CONFIG_OPTPROBES

  /* NOTE: change this value only with kprobe_mutex held */
  static bool kprobes_allow_optimization;

  /*
   * Call all pre_handler on the list, but ignores its return value.
   * This must be called from arch-dep optimized caller.
   */

  void opt_pre_handler(struct kprobe *p, struct pt_regs *regs)

  {
  	struct kprobe *kp;
  
  	list_for_each_entry_rcu(kp, &p->list, list) {
  		if (kp->pre_handler && likely(!kprobe_disabled(kp))) {
  			set_kprobe_instance(kp);

  			kp->pre_handler(kp, regs);

  		}
  		reset_kprobe_instance();
  	}
  }

  NOKPROBE_SYMBOL(opt_pre_handler);

  /* Free optimized instructions and optimized_kprobe */

  static void free_aggr_kprobe(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	op = container_of(p, struct optimized_kprobe, kp);
  	arch_remove_optimized_kprobe(op);
  	arch_remove_kprobe(p);
  	kfree(op);
  }

  /* Return true(!0) if the kprobe is ready for optimization. */
  static inline int kprobe_optready(struct kprobe *p)
  {
  	struct optimized_kprobe *op;
  
  	if (kprobe_aggrprobe(p)) {
  		op = container_of(p, struct optimized_kprobe, kp);
  		return arch_prepared_optinsn(&op->optinsn);
  	}
  
  	return 0;
  }

  /* Return true(!0) if the kprobe is disarmed. Note: p must be on hash list */
  static inline int kprobe_disarmed(struct kprobe *p)
  {
  	struct optimized_kprobe *op;
  
  	/* If kprobe is not aggr/opt probe, just return kprobe is disabled */
  	if (!kprobe_aggrprobe(p))
  		return kprobe_disabled(p);
  
  	op = container_of(p, struct optimized_kprobe, kp);
  
  	return kprobe_disabled(p) && list_empty(&op->list);
  }
  
  /* Return true(!0) if the probe is queued on (un)optimizing lists */

  static int kprobe_queued(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	if (kprobe_aggrprobe(p)) {
  		op = container_of(p, struct optimized_kprobe, kp);
  		if (!list_empty(&op->list))
  			return 1;
  	}
  	return 0;
  }

  /*
   * Return an optimized kprobe whose optimizing code replaces
   * instructions including addr (exclude breakpoint).
   */

  static struct kprobe *get_optimized_kprobe(unsigned long addr)

  {
  	int i;
  	struct kprobe *p = NULL;
  	struct optimized_kprobe *op;
  
  	/* Don't check i == 0, since that is a breakpoint case. */
  	for (i = 1; !p && i < MAX_OPTIMIZED_LENGTH; i++)
  		p = get_kprobe((void *)(addr - i));
  
  	if (p && kprobe_optready(p)) {
  		op = container_of(p, struct optimized_kprobe, kp);
  		if (arch_within_optimized_kprobe(op, addr))
  			return p;
  	}
  
  	return NULL;
  }
  
  /* Optimization staging list, protected by kprobe_mutex */
  static LIST_HEAD(optimizing_list);

  static LIST_HEAD(unoptimizing_list);

  static LIST_HEAD(freeing_list);

  
  static void kprobe_optimizer(struct work_struct *work);
  static DECLARE_DELAYED_WORK(optimizing_work, kprobe_optimizer);
  #define OPTIMIZE_DELAY 5

  /*
   * Optimize (replace a breakpoint with a jump) kprobes listed on
   * optimizing_list.
   */

  static void do_optimize_kprobes(void)

  {

  	lockdep_assert_held(&text_mutex);

  	/*
  	 * The optimization/unoptimization refers online_cpus via
  	 * stop_machine() and cpu-hotplug modifies online_cpus.
  	 * And same time, text_mutex will be held in cpu-hotplug and here.
  	 * This combination can cause a deadlock (cpu-hotplug try to lock
  	 * text_mutex but stop_machine can not be done because online_cpus
  	 * has been changed)

  	 * To avoid this deadlock, caller must have locked cpu hotplug

  	 * for preventing cpu-hotplug outside of text_mutex locking.
  	 */

  	lockdep_assert_cpus_held();
  
  	/* Optimization never be done when disarmed */
  	if (kprobes_all_disarmed || !kprobes_allow_optimization ||
  	    list_empty(&optimizing_list))
  		return;

  	arch_optimize_kprobes(&optimizing_list);

  }

  /*
   * Unoptimize (replace a jump with a breakpoint and remove the breakpoint
   * if need) kprobes listed on unoptimizing_list.
   */

  static void do_unoptimize_kprobes(void)

  {
  	struct optimized_kprobe *op, *tmp;

  	lockdep_assert_held(&text_mutex);

  	/* See comment in do_optimize_kprobes() */
  	lockdep_assert_cpus_held();

  	/* Unoptimization must be done anytime */
  	if (list_empty(&unoptimizing_list))
  		return;

  	arch_unoptimize_kprobes(&unoptimizing_list, &freeing_list);

  	/* Loop free_list for disarming */

  	list_for_each_entry_safe(op, tmp, &freeing_list, list) {

  		/* Switching from detour code to origin */
  		op->kp.flags &= ~KPROBE_FLAG_OPTIMIZED;

  		/* Disarm probes if marked disabled */
  		if (kprobe_disabled(&op->kp))
  			arch_disarm_kprobe(&op->kp);
  		if (kprobe_unused(&op->kp)) {
  			/*
  			 * Remove unused probes from hash list. After waiting
  			 * for synchronization, these probes are reclaimed.
  			 * (reclaiming is done by do_free_cleaned_kprobes.)
  			 */
  			hlist_del_rcu(&op->kp.hlist);

  		} else
  			list_del_init(&op->list);
  	}

  }
  
  /* Reclaim all kprobes on the free_list */

  static void do_free_cleaned_kprobes(void)

  {
  	struct optimized_kprobe *op, *tmp;

  	list_for_each_entry_safe(op, tmp, &freeing_list, list) {

  		list_del_init(&op->list);

  		if (WARN_ON_ONCE(!kprobe_unused(&op->kp))) {
  			/*
  			 * This must not happen, but if there is a kprobe
  			 * still in use, keep it on kprobes hash list.
  			 */
  			continue;
  		}

  		free_aggr_kprobe(&op->kp);
  	}
  }
  
  /* Start optimizer after OPTIMIZE_DELAY passed */

  static void kick_kprobe_optimizer(void)

  {

  	schedule_delayed_work(&optimizing_work, OPTIMIZE_DELAY);

  }

  /* Kprobe jump optimizer */

  static void kprobe_optimizer(struct work_struct *work)

  {

  	mutex_lock(&kprobe_mutex);

  	cpus_read_lock();

  	mutex_lock(&text_mutex);

  
  	/*

  	 * Step 1: Unoptimize kprobes and collect cleaned (unused and disarmed)
  	 * kprobes before waiting for quiesence period.
  	 */

  	do_unoptimize_kprobes();

  
  	/*

  	 * Step 2: Wait for quiesence period to ensure all potentially
  	 * preempted tasks to have normally scheduled. Because optprobe
  	 * may modify multiple instructions, there is a chance that Nth
  	 * instruction is preempted. In that case, such tasks can return
  	 * to 2nd-Nth byte of jump instruction. This wait is for avoiding it.
  	 * Note that on non-preemptive kernel, this is transparently converted
  	 * to synchronoze_sched() to wait for all interrupts to have completed.

  	 */

  	synchronize_rcu_tasks();

  	/* Step 3: Optimize kprobes after quiesence period */

  	do_optimize_kprobes();

  
  	/* Step 4: Free cleaned kprobes after quiesence period */

  	do_free_cleaned_kprobes();

  	mutex_unlock(&text_mutex);

  	cpus_read_unlock();

  	/* Step 5: Kick optimizer again if needed */

  	if (!list_empty(&optimizing_list) || !list_empty(&unoptimizing_list))

  		kick_kprobe_optimizer();

  
  	mutex_unlock(&kprobe_mutex);

  }
  
  /* Wait for completing optimization and unoptimization */

  void wait_for_kprobe_optimizer(void)

  {

  	mutex_lock(&kprobe_mutex);
  
  	while (!list_empty(&optimizing_list) || !list_empty(&unoptimizing_list)) {
  		mutex_unlock(&kprobe_mutex);
  
  		/* this will also make optimizing_work execute immmediately */
  		flush_delayed_work(&optimizing_work);
  		/* @optimizing_work might not have been queued yet, relax */
  		cpu_relax();
  
  		mutex_lock(&kprobe_mutex);
  	}
  
  	mutex_unlock(&kprobe_mutex);

  }

  static bool optprobe_queued_unopt(struct optimized_kprobe *op)
  {
  	struct optimized_kprobe *_op;
  
  	list_for_each_entry(_op, &unoptimizing_list, list) {
  		if (op == _op)
  			return true;
  	}
  
  	return false;
  }

  /* Optimize kprobe if p is ready to be optimized */

  static void optimize_kprobe(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	/* Check if the kprobe is disabled or not ready for optimization. */

  	if (!kprobe_optready(p) || !kprobes_allow_optimization ||

  	    (kprobe_disabled(p) || kprobes_all_disarmed))
  		return;

  	/* kprobes with post_handler can not be optimized */
  	if (p->post_handler)

  		return;
  
  	op = container_of(p, struct optimized_kprobe, kp);
  
  	/* Check there is no other kprobes at the optimized instructions */
  	if (arch_check_optimized_kprobe(op) < 0)
  		return;
  
  	/* Check if it is already optimized. */

  	if (op->kp.flags & KPROBE_FLAG_OPTIMIZED) {
  		if (optprobe_queued_unopt(op)) {
  			/* This is under unoptimizing. Just dequeue the probe */
  			list_del_init(&op->list);
  		}

  		return;

  	}

  	op->kp.flags |= KPROBE_FLAG_OPTIMIZED;

  	/* On unoptimizing/optimizing_list, op must have OPTIMIZED flag */
  	if (WARN_ON_ONCE(!list_empty(&op->list)))
  		return;
  
  	list_add(&op->list, &optimizing_list);
  	kick_kprobe_optimizer();

  }
  
  /* Short cut to direct unoptimizing */

  static void force_unoptimize_kprobe(struct optimized_kprobe *op)

  {

  	lockdep_assert_cpus_held();

  	arch_unoptimize_kprobe(op);

  	op->kp.flags &= ~KPROBE_FLAG_OPTIMIZED;

  }
  
  /* Unoptimize a kprobe if p is optimized */

  static void unoptimize_kprobe(struct kprobe *p, bool force)

  {
  	struct optimized_kprobe *op;

  	if (!kprobe_aggrprobe(p) || kprobe_disarmed(p))
  		return; /* This is not an optprobe nor optimized */
  
  	op = container_of(p, struct optimized_kprobe, kp);

  	if (!kprobe_optimized(p))

  		return;

  	if (!list_empty(&op->list)) {

  		if (optprobe_queued_unopt(op)) {
  			/* Queued in unoptimizing queue */
  			if (force) {
  				/*
  				 * Forcibly unoptimize the kprobe here, and queue it
  				 * in the freeing list for release afterwards.
  				 */
  				force_unoptimize_kprobe(op);
  				list_move(&op->list, &freeing_list);
  			}
  		} else {
  			/* Dequeue from the optimizing queue */
  			list_del_init(&op->list);
  			op->kp.flags &= ~KPROBE_FLAG_OPTIMIZED;
  		}

  		return;
  	}

  	/* Optimized kprobe case */

  	if (force) {

  		/* Forcibly update the code: this is a special case */
  		force_unoptimize_kprobe(op);

  	} else {

  		list_add(&op->list, &unoptimizing_list);
  		kick_kprobe_optimizer();

  	}
  }

  /* Cancel unoptimizing for reusing */

  static int reuse_unused_kprobe(struct kprobe *ap)

  {
  	struct optimized_kprobe *op;

  	/*
  	 * Unused kprobe MUST be on the way of delayed unoptimizing (means
  	 * there is still a relative jump) and disabled.
  	 */
  	op = container_of(ap, struct optimized_kprobe, kp);

  	WARN_ON_ONCE(list_empty(&op->list));

  	/* Enable the probe again */
  	ap->flags &= ~KPROBE_FLAG_DISABLED;
  	/* Optimize it again (remove from op->list) */

  	if (!kprobe_optready(ap))
  		return -EINVAL;

  	optimize_kprobe(ap);

  	return 0;

  }

  /* Remove optimized instructions */

  static void kill_optimized_kprobe(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	op = container_of(p, struct optimized_kprobe, kp);

  	if (!list_empty(&op->list))
  		/* Dequeue from the (un)optimization queue */

  		list_del_init(&op->list);

  	op->kp.flags &= ~KPROBE_FLAG_OPTIMIZED;

  
  	if (kprobe_unused(p)) {
  		/* Enqueue if it is unused */
  		list_add(&op->list, &freeing_list);
  		/*
  		 * Remove unused probes from the hash list. After waiting
  		 * for synchronization, this probe is reclaimed.
  		 * (reclaiming is done by do_free_cleaned_kprobes().)
  		 */
  		hlist_del_rcu(&op->kp.hlist);
  	}

  	/* Don't touch the code, because it is already freed. */

  	arch_remove_optimized_kprobe(op);
  }

  static inline
  void __prepare_optimized_kprobe(struct optimized_kprobe *op, struct kprobe *p)
  {
  	if (!kprobe_ftrace(p))
  		arch_prepare_optimized_kprobe(op, p);
  }

  /* Try to prepare optimized instructions */

  static void prepare_optimized_kprobe(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	op = container_of(p, struct optimized_kprobe, kp);

  	__prepare_optimized_kprobe(op, p);

  }

  /* Allocate new optimized_kprobe and try to prepare optimized instructions */

  static struct kprobe *alloc_aggr_kprobe(struct kprobe *p)

  {
  	struct optimized_kprobe *op;
  
  	op = kzalloc(sizeof(struct optimized_kprobe), GFP_KERNEL);
  	if (!op)
  		return NULL;
  
  	INIT_LIST_HEAD(&op->list);
  	op->kp.addr = p->addr;

  	__prepare_optimized_kprobe(op, p);

  
  	return &op->kp;
  }

  static void init_aggr_kprobe(struct kprobe *ap, struct kprobe *p);

  
  /*
   * Prepare an optimized_kprobe and optimize it
   * NOTE: p must be a normal registered kprobe
   */

  static void try_to_optimize_kprobe(struct kprobe *p)

  {
  	struct kprobe *ap;
  	struct optimized_kprobe *op;

  	/* Impossible to optimize ftrace-based kprobe */
  	if (kprobe_ftrace(p))
  		return;

  	/* For preparing optimization, jump_label_text_reserved() is called */

  	cpus_read_lock();

  	jump_label_lock();
  	mutex_lock(&text_mutex);

  	ap = alloc_aggr_kprobe(p);
  	if (!ap)

  		goto out;

  
  	op = container_of(ap, struct optimized_kprobe, kp);
  	if (!arch_prepared_optinsn(&op->optinsn)) {
  		/* If failed to setup optimizing, fallback to kprobe */

  		arch_remove_optimized_kprobe(op);
  		kfree(op);

  		goto out;

  	}
  
  	init_aggr_kprobe(ap, p);

  	optimize_kprobe(ap);	/* This just kicks optimizer thread */
  
  out:
  	mutex_unlock(&text_mutex);
  	jump_label_unlock();

  	cpus_read_unlock();

  }

  #ifdef CONFIG_SYSCTL

  static void optimize_all_kprobes(void)

  {
  	struct hlist_head *head;

  	struct kprobe *p;
  	unsigned int i;

  	mutex_lock(&kprobe_mutex);

  	/* If optimization is already allowed, just return */
  	if (kprobes_allow_optimization)

  		goto out;

  	cpus_read_lock();

  	kprobes_allow_optimization = true;

  	for (i = 0; i < KPROBE_TABLE_SIZE; i++) {
  		head = &kprobe_table[i];

  		hlist_for_each_entry(p, head, hlist)

  			if (!kprobe_disabled(p))
  				optimize_kprobe(p);
  	}

  	cpus_read_unlock();

  	printk(KERN_INFO "Kprobes globally optimized
  ");

  out:
  	mutex_unlock(&kprobe_mutex);

  }

  static void unoptimize_all_kprobes(void)

  {
  	struct hlist_head *head;

  	struct kprobe *p;
  	unsigned int i;

  	mutex_lock(&kprobe_mutex);

  	/* If optimization is already prohibited, just return */

  	if (!kprobes_allow_optimization) {
  		mutex_unlock(&kprobe_mutex);

  		return;

  	}

  	cpus_read_lock();

  	kprobes_allow_optimization = false;

  	for (i = 0; i < KPROBE_TABLE_SIZE; i++) {
  		head = &kprobe_table[i];

  		hlist_for_each_entry(p, head, hlist) {

  			if (!kprobe_disabled(p))

  				unoptimize_kprobe(p, false);

  		}
  	}

  	cpus_read_unlock();

  	mutex_unlock(&kprobe_mutex);

  	/* Wait for unoptimizing completion */
  	wait_for_kprobe_optimizer();
  	printk(KERN_INFO "Kprobes globally unoptimized
  ");

  }

  static DEFINE_MUTEX(kprobe_sysctl_mutex);

  int sysctl_kprobes_optimization;
  int proc_kprobes_optimization_handler(struct ctl_table *table, int write,

  				      void *buffer, size_t *length,

  				      loff_t *ppos)
  {
  	int ret;

  	mutex_lock(&kprobe_sysctl_mutex);

  	sysctl_kprobes_optimization = kprobes_allow_optimization ? 1 : 0;
  	ret = proc_dointvec_minmax(table, write, buffer, length, ppos);
  
  	if (sysctl_kprobes_optimization)
  		optimize_all_kprobes();
  	else
  		unoptimize_all_kprobes();

  	mutex_unlock(&kprobe_sysctl_mutex);

  
  	return ret;
  }
  #endif /* CONFIG_SYSCTL */

  /* Put a breakpoint for a probe. Must be called with text_mutex locked */

  static void __arm_kprobe(struct kprobe *p)

  {

  	struct kprobe *_p;

  
  	/* Check collision with other optimized kprobes */

  	_p = get_optimized_kprobe((unsigned long)p->addr);
  	if (unlikely(_p))

  		/* Fallback to unoptimized kprobe */
  		unoptimize_kprobe(_p, true);

  
  	arch_arm_kprobe(p);
  	optimize_kprobe(p);	/* Try to optimize (add kprobe to a list) */
  }

  /* Remove the breakpoint of a probe. Must be called with text_mutex locked */

  static void __disarm_kprobe(struct kprobe *p, bool reopt)

  {

  	struct kprobe *_p;

  	/* Try to unoptimize */
  	unoptimize_kprobe(p, kprobes_all_disarmed);

  	if (!kprobe_queued(p)) {
  		arch_disarm_kprobe(p);
  		/* If another kprobe was blocked, optimize it. */
  		_p = get_optimized_kprobe((unsigned long)p->addr);
  		if (unlikely(_p) && reopt)
  			optimize_kprobe(_p);
  	}
  	/* TODO: reoptimize others after unoptimized this probe */

  }
  
  #else /* !CONFIG_OPTPROBES */
  
  #define optimize_kprobe(p)			do {} while (0)

  #define unoptimize_kprobe(p, f)			do {} while (0)

  #define kill_optimized_kprobe(p)		do {} while (0)
  #define prepare_optimized_kprobe(p)		do {} while (0)
  #define try_to_optimize_kprobe(p)		do {} while (0)
  #define __arm_kprobe(p)				arch_arm_kprobe(p)

  #define __disarm_kprobe(p, o)			arch_disarm_kprobe(p)
  #define kprobe_disarmed(p)			kprobe_disabled(p)
  #define wait_for_kprobe_optimizer()		do {} while (0)

  static int reuse_unused_kprobe(struct kprobe *ap)

  {

  	/*
  	 * If the optimized kprobe is NOT supported, the aggr kprobe is
  	 * released at the same time that the last aggregated kprobe is
  	 * unregistered.
  	 * Thus there should be no chance to reuse unused kprobe.
  	 */

  	printk(KERN_ERR "Error: There should be no unused kprobe here.
  ");

  	return -EINVAL;

  }

  static void free_aggr_kprobe(struct kprobe *p)

  {

  	arch_remove_kprobe(p);

  	kfree(p);
  }

  static struct kprobe *alloc_aggr_kprobe(struct kprobe *p)

  {
  	return kzalloc(sizeof(struct kprobe), GFP_KERNEL);
  }
  #endif /* CONFIG_OPTPROBES */

  #ifdef CONFIG_KPROBES_ON_FTRACE

  static struct ftrace_ops kprobe_ftrace_ops __read_mostly = {

  	.func = kprobe_ftrace_handler,

  	.flags = FTRACE_OPS_FL_SAVE_REGS,
  };
  
  static struct ftrace_ops kprobe_ipmodify_ops __read_mostly = {
  	.func = kprobe_ftrace_handler,

  	.flags = FTRACE_OPS_FL_SAVE_REGS | FTRACE_OPS_FL_IPMODIFY,

  };

  
  static int kprobe_ipmodify_enabled;

  static int kprobe_ftrace_enabled;
  
  /* Must ensure p->addr is really on ftrace */

  static int prepare_kprobe(struct kprobe *p)

  {
  	if (!kprobe_ftrace(p))
  		return arch_prepare_kprobe(p);
  
  	return arch_prepare_kprobe_ftrace(p);
  }
  
  /* Caller must lock kprobe_mutex */

  static int __arm_kprobe_ftrace(struct kprobe *p, struct ftrace_ops *ops,
  			       int *cnt)

  {

  	int ret = 0;

  	ret = ftrace_set_filter_ip(ops, (unsigned long)p->addr, 0, 0);

  	if (ret) {

  		pr_debug("Failed to arm kprobe-ftrace at %pS (%d)
  ",
  			 p->addr, ret);

  		return ret;
  	}

  	if (*cnt == 0) {
  		ret = register_ftrace_function(ops);

  		if (ret) {
  			pr_debug("Failed to init kprobe-ftrace (%d)
  ", ret);
  			goto err_ftrace;
  		}

  	}

  	(*cnt)++;

  	return ret;
  
  err_ftrace:
  	/*

  	 * At this point, sinec ops is not registered, we should be sefe from
  	 * registering empty filter.

  	 */

  	ftrace_set_filter_ip(ops, (unsigned long)p->addr, 1, 0);

  	return ret;

  }

  static int arm_kprobe_ftrace(struct kprobe *p)
  {
  	bool ipmodify = (p->post_handler != NULL);
  
  	return __arm_kprobe_ftrace(p,
  		ipmodify ? &kprobe_ipmodify_ops : &kprobe_ftrace_ops,
  		ipmodify ? &kprobe_ipmodify_enabled : &kprobe_ftrace_enabled);
  }

  /* Caller must lock kprobe_mutex */

  static int __disarm_kprobe_ftrace(struct kprobe *p, struct ftrace_ops *ops,
  				  int *cnt)

  {

  	int ret = 0;

  	if (*cnt == 1) {
  		ret = unregister_ftrace_function(ops);

  		if (WARN(ret < 0, "Failed to unregister kprobe-ftrace (%d)
  ", ret))
  			return ret;

  	}

  	(*cnt)--;

  	ret = ftrace_set_filter_ip(ops, (unsigned long)p->addr, 1, 0);

  	WARN_ONCE(ret < 0, "Failed to disarm kprobe-ftrace at %pS (%d)
  ",
  		  p->addr, ret);

  	return ret;

  }

  
  static int disarm_kprobe_ftrace(struct kprobe *p)
  {
  	bool ipmodify = (p->post_handler != NULL);
  
  	return __disarm_kprobe_ftrace(p,
  		ipmodify ? &kprobe_ipmodify_ops : &kprobe_ftrace_ops,
  		ipmodify ? &kprobe_ipmodify_enabled : &kprobe_ftrace_enabled);
  }

  #else	/* !CONFIG_KPROBES_ON_FTRACE */

  static inline int prepare_kprobe(struct kprobe *p)
  {
  	return arch_prepare_kprobe(p);
  }
  
  static inline int arm_kprobe_ftrace(struct kprobe *p)
  {
  	return -ENODEV;
  }
  
  static inline int disarm_kprobe_ftrace(struct kprobe *p)
  {
  	return -ENODEV;
  }

  #endif

  /* Arm a kprobe with text_mutex */

  static int arm_kprobe(struct kprobe *kp)

  {

  	if (unlikely(kprobe_ftrace(kp)))
  		return arm_kprobe_ftrace(kp);

  	cpus_read_lock();

  	mutex_lock(&text_mutex);

  	__arm_kprobe(kp);

  	mutex_unlock(&text_mutex);

  	cpus_read_unlock();

  
  	return 0;

  }
  
  /* Disarm a kprobe with text_mutex */

  static int disarm_kprobe(struct kprobe *kp, bool reopt)

  {

  	if (unlikely(kprobe_ftrace(kp)))
  		return disarm_kprobe_ftrace(kp);

  
  	cpus_read_lock();

  	mutex_lock(&text_mutex);

  	__disarm_kprobe(kp, reopt);

  	mutex_unlock(&text_mutex);

  	cpus_read_unlock();

  
  	return 0;

  }

  /*
   * Aggregate handlers for multiple kprobes support - these handlers
   * take care of invoking the individual kprobe handlers on p->list
   */

  static int aggr_pre_handler(struct kprobe *p, struct pt_regs *regs)

  {
  	struct kprobe *kp;

  	list_for_each_entry_rcu(kp, &p->list, list) {

  		if (kp->pre_handler && likely(!kprobe_disabled(kp))) {

  			set_kprobe_instance(kp);

  			if (kp->pre_handler(kp, regs))
  				return 1;

  		}

  		reset_kprobe_instance();

  	}
  	return 0;
  }

  NOKPROBE_SYMBOL(aggr_pre_handler);

  static void aggr_post_handler(struct kprobe *p, struct pt_regs *regs,
  			      unsigned long flags)

  {
  	struct kprobe *kp;

  	list_for_each_entry_rcu(kp, &p->list, list) {

  		if (kp->post_handler && likely(!kprobe_disabled(kp))) {

  			set_kprobe_instance(kp);

  			kp->post_handler(kp, regs, flags);

  			reset_kprobe_instance();

  		}
  	}

  }

  NOKPROBE_SYMBOL(aggr_post_handler);

  static int aggr_fault_handler(struct kprobe *p, struct pt_regs *regs,
  			      int trapnr)

  {

  	struct kprobe *cur = __this_cpu_read(kprobe_instance);

  	/*
  	 * if we faulted "during" the execution of a user specified
  	 * probe handler, invoke just that probe's fault handler
  	 */

  	if (cur && cur->fault_handler) {
  		if (cur->fault_handler(cur, regs, trapnr))

  			return 1;
  	}
  	return 0;
  }

  NOKPROBE_SYMBOL(aggr_fault_handler);

  /* Walks the list and increments nmissed count for multiprobe case */

  void kprobes_inc_nmissed_count(struct kprobe *p)

  {
  	struct kprobe *kp;

  	if (!kprobe_aggrprobe(p)) {

  		p->nmissed++;
  	} else {
  		list_for_each_entry_rcu(kp, &p->list, list)
  			kp->nmissed++;
  	}
  	return;
  }

  NOKPROBE_SYMBOL(kprobes_inc_nmissed_count);

  static void recycle_rp_inst(struct kretprobe_instance *ri)

  {

  	struct kretprobe *rp = ri->rp;

  	/* remove rp inst off the rprobe_inst_table */
  	hlist_del(&ri->hlist);

  	INIT_HLIST_NODE(&ri->hlist);
  	if (likely(rp)) {

  		raw_spin_lock(&rp->lock);

  		hlist_add_head(&ri->hlist, &rp->free_instances);

  		raw_spin_unlock(&rp->lock);

  	} else

  		kfree_rcu(ri, rcu);

  }

  NOKPROBE_SYMBOL(recycle_rp_inst);

  static void kretprobe_hash_lock(struct task_struct *tsk,

  			 struct hlist_head **head, unsigned long *flags)

  __acquires(hlist_lock)

  {
  	unsigned long hash = hash_ptr(tsk, KPROBE_HASH_BITS);

  	raw_spinlock_t *hlist_lock;

  
  	*head = &kretprobe_inst_table[hash];
  	hlist_lock = kretprobe_table_lock_ptr(hash);

  	/*
  	 * Nested is a workaround that will soon not be needed.
  	 * There's other protections that make sure the same lock
  	 * is not taken on the same CPU that lockdep is unaware of.
  	 * Differentiate when it is taken in NMI context.
  	 */
  	raw_spin_lock_irqsave_nested(hlist_lock, *flags, !!in_nmi());

  }

  NOKPROBE_SYMBOL(kretprobe_hash_lock);

  static void kretprobe_table_lock(unsigned long hash,
  				 unsigned long *flags)

  __acquires(hlist_lock)

  {

  	raw_spinlock_t *hlist_lock = kretprobe_table_lock_ptr(hash);

  	/*
  	 * Nested is a workaround that will soon not be needed.
  	 * There's other protections that make sure the same lock
  	 * is not taken on the same CPU that lockdep is unaware of.
  	 * Differentiate when it is taken in NMI context.
  	 */
  	raw_spin_lock_irqsave_nested(hlist_lock, *flags, !!in_nmi());

  }

  NOKPROBE_SYMBOL(kretprobe_table_lock);

  static void kretprobe_hash_unlock(struct task_struct *tsk,

  			   unsigned long *flags)

  __releases(hlist_lock)

  {
  	unsigned long hash = hash_ptr(tsk, KPROBE_HASH_BITS);

  	raw_spinlock_t *hlist_lock;

  
  	hlist_lock = kretprobe_table_lock_ptr(hash);

  	raw_spin_unlock_irqrestore(hlist_lock, *flags);

  }

  NOKPROBE_SYMBOL(kretprobe_hash_unlock);

  static void kretprobe_table_unlock(unsigned long hash,
  				   unsigned long *flags)

  __releases(hlist_lock)

  {

  	raw_spinlock_t *hlist_lock = kretprobe_table_lock_ptr(hash);
  	raw_spin_unlock_irqrestore(hlist_lock, *flags);

  }

  NOKPROBE_SYMBOL(kretprobe_table_unlock);

  static struct kprobe kprobe_busy = {

  	.addr = (void *) get_kprobe,
  };
  
  void kprobe_busy_begin(void)
  {
  	struct kprobe_ctlblk *kcb;
  
  	preempt_disable();
  	__this_cpu_write(current_kprobe, &kprobe_busy);
  	kcb = get_kprobe_ctlblk();
  	kcb->kprobe_status = KPROBE_HIT_ACTIVE;
  }
  
  void kprobe_busy_end(void)
  {
  	__this_cpu_write(current_kprobe, NULL);
  	preempt_enable();
  }

  /*

   * This function is called from finish_task_switch when task tk becomes dead,
   * so that we can recycle any function-return probe instances associated
   * with this task. These left over instances represent probed functions
   * that have been called but will never return.

   */

  void kprobe_flush_task(struct task_struct *tk)

  {

  	struct kretprobe_instance *ri;

  	struct hlist_head *head;

  	struct hlist_node *tmp;

  	unsigned long hash, flags = 0;

  	if (unlikely(!kprobes_initialized))
  		/* Early boot.  kretprobe_table_locks not yet initialized. */
  		return;

  	kprobe_busy_begin();

  	hash = hash_ptr(tk, KPROBE_HASH_BITS);
  	head = &kretprobe_inst_table[hash];
  	kretprobe_table_lock(hash, &flags);

  	hlist_for_each_entry_safe(ri, tmp, head, hlist) {

  		if (ri->task == tk)

  			recycle_rp_inst(ri);

  	}

  	kretprobe_table_unlock(hash, &flags);

  
  	kprobe_busy_end();

  }

  NOKPROBE_SYMBOL(kprobe_flush_task);

  static inline void free_rp_inst(struct kretprobe *rp)
  {
  	struct kretprobe_instance *ri;

  	struct hlist_node *next;

  	hlist_for_each_entry_safe(ri, next, &rp->free_instances, hlist) {

  		hlist_del(&ri->hlist);

  		kfree(ri);
  	}
  }

  static void cleanup_rp_inst(struct kretprobe *rp)

  {

  	unsigned long flags, hash;

  	struct kretprobe_instance *ri;

  	struct hlist_node *next;

  	struct hlist_head *head;

  	/* To avoid recursive kretprobe by NMI, set kprobe busy here */
  	kprobe_busy_begin();

  	for (hash = 0; hash < KPROBE_TABLE_SIZE; hash++) {
  		kretprobe_table_lock(hash, &flags);
  		head = &kretprobe_inst_table[hash];

  		hlist_for_each_entry_safe(ri, next, head, hlist) {

  			if (ri->rp == rp)
  				ri->rp = NULL;
  		}
  		kretprobe_table_unlock(hash, &flags);

  	}

  	kprobe_busy_end();

  	free_rp_inst(rp);
  }

  NOKPROBE_SYMBOL(cleanup_rp_inst);

  /* Add the new probe to ap->list */

  static int add_new_kprobe(struct kprobe *ap, struct kprobe *p)

  {

  	if (p->post_handler)

  		unoptimize_kprobe(ap, true);	/* Fall back to normal kprobe */

  	list_add_rcu(&p->list, &ap->list);

  	if (p->post_handler && !ap->post_handler)
  		ap->post_handler = aggr_post_handler;

  	return 0;
  }
  
  /*

   * Fill in the required fields of the "manager kprobe". Replace the
   * earlier kprobe in the hlist with the manager kprobe
   */

  static void init_aggr_kprobe(struct kprobe *ap, struct kprobe *p)

  {

  	/* Copy p's insn slot to ap */

  	copy_kprobe(p, ap);

  	flush_insn_slot(ap);