[RFC PATCH 15/26] x86/alternatives: Non-emulated text poking

[Ankur Arora]

Patching at runtime needs to handle interdependent pv-ops: as an example,
lock.queued_lock_slowpath(), lock.queued_lock_unlock() and the other
pv_lock_ops are paired and so need to be updated atomically. This is
difficult with emulation because non-patching CPUs could be executing in
critical sections.
(We could apply INT3 everywhere first and then use RCU to force a
barrier but given that spinlocks are everywhere, it still might mean a
lot of time in emulation.)

Second, locking operations can be called from interrupt handlers which
means we cannot trivially use IPIs to introduce a pipeline sync step on
non-patching CPUs.

Third, some pv-ops can be inlined and so we would need to emulate a
broader set of operations than CALL, JMP, NOP*.

Introduce the core state-machine with the actual poking and pipeline
sync stubbed out. This executes via stop_machine() with the primary CPU
carrying out a text_poke_bp() style three-staged algorithm.

The control flow diagram below shows CPU0 as the primary which does the
patching, while the rest of the CPUs (CPUx) execute the sync loop in
text_poke_sync_finish().

 CPU0				    CPUx
 ----                               ----

 patch_worker()			    patch_worker()

   /* Traversal, insn-gen */	      text_poke_sync_finish()
   tps.patch_worker()		      /*
  				       * wait until:
     /* for each patch-site */ 	       *  tps->state == PATCH_DONE
     text_poke_site()		       */
       poke_sync()

  	   ...				       ...

   smp_store_release(&tps->state, PATCH_DONE)

Commits further on flesh out the rest of the code.

Signed-off-by: Ankur Arora <ankur.a.arora@xxxxxxxxxx>
---
sync_one() uses the following for pipeline synchronization:

+       if (in_nmi())
+               cpuid_eax(1);
+       else
+               sync_core();

The if (in_nmi()) clause is meant to be executed from NMI contexts.
Reading through past LKML discussions cpuid_eax() is probably a
bad choice -- at least in so far as Xen PV is concerned. What
would be a good primitive to use insead?

Also, given that we do handle the nested NMI case, does it make sense
to just use native_iret() (via sync_core()) in NMI contexts well?

---
 arch/x86/kernel/alternative.c | 247 ++++++++++++++++++++++++++++++++++
 1 file changed, 247 insertions(+)

diff --git a/arch/x86/kernel/alternative.c b/arch/x86/kernel/alternative.c
index 004fe86f463f..452d4081eded 100644
--- a/arch/x86/kernel/alternative.c
+++ b/arch/x86/kernel/alternative.c
@@ -979,6 +979,26 @@ void text_poke_sync(void)
 	on_each_cpu(do_sync_core, NULL, 1);
 }
 
+static void __maybe_unused sync_one(void)
+{
+	/*
+	 * We might be executing in NMI context, and so cannot use
+	 * IRET as a synchronizing instruction.
+	 *
+	 * We could use native_write_cr2() but that is not guaranteed
+	 * to work on Xen-PV -- it is emulated by Xen and might not
+	 * execute an iret (or similar synchronizing instruction)
+	 * internally.
+	 *
+	 * cpuid() would trap as well. Unclear if that's a solution
+	 * either.
+	 */
+	if (in_nmi())
+		cpuid_eax(1);
+	else
+		sync_core();
+}
+
 struct text_poke_loc {
 	s32 rel_addr; /* addr := _stext + rel_addr */
 	union {
@@ -1351,6 +1371,233 @@ void __ref text_poke_bp(void *addr, const void *opcode, size_t len, const void *
 	text_poke_bp_batch(&tp, 1);
 }
 
+struct text_poke_state;
+typedef void (*patch_worker_t)(struct text_poke_state *tps);
+
+/*
+ *                        +-----------possible-BP----------+
+ *                        |                                |
+ *         +--write-INT3--+   +--suffix--+   +-insn-prefix-+
+ *        /               | _/           |__/              |
+ *       /                v'             v                 v
+ * PATCH_SYNC_0    PATCH_SYNC_1    PATCH_SYNC_2   *PATCH_SYNC_DONE*
+ *       \                                                    |`----> PATCH_DONE
+ *        `----------<---------<---------<---------<----------+
+ *
+ * We start in state PATCH_SYNC_DONE and loop through PATCH_SYNC_* states
+ * to end at PATCH_DONE. The primary drives these in text_poke_site()
+ * with patch_worker() making the final transition to PATCH_DONE.
+ * All transitions but the last iteration need to be globally observed.
+ *
+ * On secondary CPUs, text_poke_sync_finish() waits in a cpu_relax()
+ * loop waiting for a transition to PATCH_SYNC_0 at which point it would
+ * start observing transitions until PATCH_SYNC_DONE.
+ * Eventually the master moves to PATCH_DONE and secondary CPUs finish.
+ */
+enum patch_state {
+	/*
+	 * Add an artificial state that we can do a bitwise operation
+	 * over all the PATCH_SYNC_* states.
+	 */
+	PATCH_SYNC_x = 4,
+	PATCH_SYNC_0 = PATCH_SYNC_x | 0,	/* Serialize INT3 */
+	PATCH_SYNC_1 = PATCH_SYNC_x | 1,	/* Serialize rest */
+	PATCH_SYNC_2 = PATCH_SYNC_x | 2,	/* Serialize first opcode */
+	PATCH_SYNC_DONE = PATCH_SYNC_x | 3,	/* Site done, and start state */
+
+	PATCH_DONE = 8,				/* End state */
+};
+
+/*
+ * State for driving text-poking via stop_machine().
+ */
+struct text_poke_state {
+	/* Whatever we are poking */
+	void *stage;
+
+	/* Modules to be processed. */
+	struct list_head *head;
+
+	/*
+	 * Accesses to sync_ack_map are ordered by the primary
+	 * via tps.state.
+	 */
+	struct cpumask sync_ack_map;
+
+	/*
+	 * Generates insn sequences for call-sites to be patched and
+	 * calls text_poke_site() to do the actual poking.
+	 */
+	patch_worker_t	patch_worker;
+
+	/*
+	 * Where are we in the patching state-machine.
+	 */
+	enum patch_state state;
+
+	unsigned int primary_cpu; /* CPU doing the patching. */
+	unsigned int num_acks; /* Number of Acks needed. */
+};
+
+static struct text_poke_state text_poke_state;
+
+/**
+ * poke_sync() - transitions to the specified state.
+ *
+ * @tps - struct text_poke_state *
+ * @state - one of PATCH_SYNC_* states
+ * @offset - offset to be patched
+ * @insns - insns to write
+ * @len - length of insn sequence
+ */
+static void poke_sync(struct text_poke_state *tps, int state, int offset,
+		      const char *insns, int len)
+{
+	/*
+	 * STUB: no patching or synchronization, just go through the
+	 * motions.
+	 */
+	smp_store_release(&tps->state, state);
+}
+
+/**
+ * text_poke_site() - called on the primary to patch a single call site.
+ *
+ * Returns after switching tps->state to PATCH_SYNC_DONE.
+ */
+static void __maybe_unused text_poke_site(struct text_poke_state *tps,
+					  struct text_poke_loc *tp)
+{
+	const unsigned char int3 = INT3_INSN_OPCODE;
+	temp_mm_state_t prev_mm;
+	pte_t *ptep;
+	int offset;
+
+	__text_poke_map(text_poke_addr(tp), tp->native.len, &prev_mm, &ptep);
+
+	offset = offset_in_page(text_poke_addr(tp));
+
+	/*
+	 * All secondary CPUs are waiting in tps->state == PATCH_SYNC_DONE
+	 * to move to PATCH_SYNC_0. Poke the INT3 and wait until all CPUs
+	 * are known to have observed PATCH_SYNC_0.
+	 *
+	 * The earliest we can hit an INT3 is just after the first poke.
+	 */
+	poke_sync(tps, PATCH_SYNC_0, offset, &int3, INT3_INSN_SIZE);
+
+	/* Poke remaining */
+	poke_sync(tps, PATCH_SYNC_1, offset + INT3_INSN_SIZE,
+		  tp->text + INT3_INSN_SIZE, tp->native.len - INT3_INSN_SIZE);
+
+	/*
+	 * Replace the INT3 with the first opcode and force the serializing
+	 * instruction for the last time. Any secondaries in the BP
+	 * handler should be able to move past the INT3 handler after this.
+	 * (See poke_int3_native() for details on this.)
+	 */
+	poke_sync(tps, PATCH_SYNC_2, offset, tp->text, INT3_INSN_SIZE);
+
+	/*
+	 * Force all CPUS to observe PATCH_SYNC_DONE (in the BP handler or
+	 * in text_poke_site()), so they know that this iteration is done
+	 * and it is safe to exit the wait-until-a-sync-is-required loop.
+	 */
+	poke_sync(tps, PATCH_SYNC_DONE, 0, NULL, 0);
+
+	/*
+	 * Unmap the poking_addr, poking_mm.
+	 */
+	__text_poke_unmap(text_poke_addr(tp), tp->text, tp->native.len,
+			  &prev_mm, ptep);
+}
+
+/**
+ * text_poke_sync_finish() -- called to synchronize the CPU pipeline
+ * on secondary CPUs for all patch sites.
+ *
+ * Called in thread context with tps->state == PATCH_SYNC_DONE.
+ * Returns with tps->state == PATCH_DONE.
+ */
+static void text_poke_sync_finish(struct text_poke_state *tps)
+{
+	while (true) {
+		enum patch_state state;
+
+		state = READ_ONCE(tps->state);
+
+		/*
+		 * We aren't doing any actual poking yet, so we don't
+		 * handle any other states.
+		 */
+		if (state == PATCH_DONE)
+			break;
+
+		/*
+		 * Relax here while the primary makes up its mind on
+		 * whether it is done or not.
+		 */
+		cpu_relax();
+	}
+}
+
+static int patch_worker(void *t)
+{
+	int cpu = smp_processor_id();
+	struct text_poke_state *tps = t;
+
+	if (cpu == tps->primary_cpu) {
+		/*
+		 * Generates insns and calls text_poke_site() to do the poking
+		 * and sync.
+		 */
+		tps->patch_worker(tps);
+
+		/*
+		 * We are done patching. Switch the state to PATCH_DONE
+		 * so the secondaries can exit.
+		 */
+		smp_store_release(&tps->state, PATCH_DONE);
+	} else {
+		/* Secondary CPUs spin in a sync_core() state-machine. */
+		text_poke_sync_finish(tps);
+	}
+	return 0;
+}
+
+/**
+ * text_poke_late() -- late patching via stop_machine().
+ *
+ * Called holding the text_mutex.
+ *
+ * Return: 0 on success, -errno on failure.
+ */
+static int __maybe_unused text_poke_late(patch_worker_t worker, void *stage)
+{
+	int ret;
+
+	lockdep_assert_held(&text_mutex);
+
+	if (system_state != SYSTEM_RUNNING)
+		return -EINVAL;
+
+	text_poke_state.stage = stage;
+	text_poke_state.num_acks = cpumask_weight(cpu_online_mask);
+	text_poke_state.head = &alt_modules;
+
+	text_poke_state.patch_worker = worker;
+	text_poke_state.state = PATCH_SYNC_DONE; /* Start state */
+	text_poke_state.primary_cpu = smp_processor_id();
+
+	/*
+	 * Run the worker on all online CPUs. Don't need to do anything
+	 * for offline CPUs as they come back online with a clean cache.
+	 */
+	ret = stop_machine(patch_worker, &text_poke_state, cpu_online_mask);
+
+	return ret;
+}
+
 #ifdef CONFIG_PARAVIRT_RUNTIME
 struct paravirt_stage_entry {
 	void *dest;	/* pv_op destination */
-- 
2.20.1