[PATCH v2 1/2] livepatch: introduce shadow variable API

[Joe Lawrence]

Add exported API for livepatch modules:

  klp_shadow_get()
  klp_shadow_attach()
  klp_shadow_get_or_attach()
  klp_shadow_detach()
  klp_shadow_detach_all()

that implement "shadow" variables, which allow callers to associate new
shadow fields to existing data structures.  This is intended to be used
by livepatch modules seeking to emulate additions to data structure
definitions.

See Documentation/livepatch/shadow-vars.txt for a summary of the new
shadow variable API, including a few common use cases.

Signed-off-by: Joe Lawrence <joe.lawrence@xxxxxxxxxx>
---
 Documentation/livepatch/shadow-vars.txt | 156 +++++++++++++++++++
 include/linux/livepatch.h               |   8 +
 kernel/livepatch/Makefile               |   2 +-
 kernel/livepatch/shadow.c               | 257 ++++++++++++++++++++++++++++++++
 4 files changed, 422 insertions(+), 1 deletion(-)
 create mode 100644 Documentation/livepatch/shadow-vars.txt
 create mode 100644 kernel/livepatch/shadow.c

diff --git a/Documentation/livepatch/shadow-vars.txt b/Documentation/livepatch/shadow-vars.txt
new file mode 100644
index 000000000000..7f28982e6b1c
--- /dev/null
+++ b/Documentation/livepatch/shadow-vars.txt
@@ -0,0 +1,156 @@
+Shadow Variables
+================
+
+Shadow variables are a simple way for livepatch modules to associate new
+"shadow" data to existing data structures.  Original data structures
+(both their definition and storage) are left unmodified and "new" data
+is allocated separately.  A shadow variable hashtable associates a
+string key, enumeration pair with a pointer to the new data.
+
+
+Brief API summary
+-----------------
+
+See the full API usage docbook notes in the livepatch/shadow.c
+implementation.
+
+An in-kernel hashtable references all of the shadow variables.  These
+references are stored/retrieved through a <obj, num> key pair.
+
+* The klp_shadow variable data structure encapsulates both tracking
+meta-data and shadow-data:
+  - meta-data
+    - obj - pointer to original data
+    - num - numerical description of new data
+  - new_data[] - storage for shadow data
+
+* klp_shadow_attach() - allocate and add a new shadow variable:
+  - allocate a new shadow variable
+  - push a <obj, num> key pair into hashtable
+
+* klp_shadow_get() - retrieve a shadow variable new_data pointer
+  - search hashtable for <obj, num> key pair
+
+* klp_shadow_get_or_attach() - get existing or attach a new shadow variable
+  - search hashtable for <obj, num> key pair
+  - if not found, call klp_shadow_attach()
+
+* klp_shadow_detach() - detach and free a <obj, num> shadow variable
+  - find and remove any <obj, num> references from hashtable
+    - if found, release shadow variable
+
+* klp_shadow_detach() - detach and free all <*, num> shadow variables
+  - find and remove any <*, num> references from hashtable
+    - if found, release shadow variable
+
+
+Use cases
+---------
+
+See the example shadow variable livepatch modules in samples/livepatch
+for full working demonstrations.
+
+Example 1: Commit 1d147bfa6429 ("mac80211: fix AP powersave TX vs.
+wakeup race") added a spinlock to net/mac80211/sta_info.h :: struct
+sta_info.  Implementing this change with a shadow variable is
+straightforward.
+
+Allocation - when a host sta_info structure is allocated, attach a
+shadow variable copy of the ps_lock:
+
+#define PS_LOCK 1
+struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
+				const u8 *addr, gfp_t gfp)
+{
+	struct sta_info *sta;
+	spinlock_t *ps_lock;
+	...
+	sta = kzalloc(sizeof(*sta) + hw->sta_data_size, gfp);
+	...
+	ps_lock = klp_shadow_attach(sta, PS_LOCK, NULL, sizeof(*ps_lock), gfp);
+	if (!ps_lock)
+		goto shadow_fail;
+	spin_lock_init(ps_lock);
+	...
+
+Usage - when using the shadow spinlock, query the shadow variable API to
+retrieve it:
+
+void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta)
+{
+	spinlock_t *ps_lock;
+	...
+	/* sync with ieee80211_tx_h_unicast_ps_buf */
+	ps_lock = klp_shadow_get(sta, "ps_lock");
+	if (ps_lock)
+		spin_lock(ps_lock);
+	...
+	if (ps_lock)
+		spin_unlock(ps_lock);
+	...
+
+Release - when the host sta_info structure is freed, first detach the
+shadow variable and then free the shadow spinlock:
+
+void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
+{
+	spinlock_t *ps_lock;
+	...
+	ps_lock = klp_shadow_get(sta, "ps_lock");
+	if (ps_lock)
+		klp_shadow_detach(sta, "ps_lock");
+
+	kfree(sta);
+
+
+Example 2: Commit 82486aa6f1b9 ("ipv4: restore rt->fi for reference
+counting") added a struct fib_info pointer to include/net/route.h ::
+struct rtable. A shadow variable can be used to implement the new
+pointer.
+
+This implementation diverges from the original commit, as it can attach
+the shadow variable when the code actually uses it:
+
+#define FIB_INFO 1
+static void rt_init_metrics(struct rtable *rt, struct fib_info *fi)
+{
+	if (fi->fib_metrics != (u32 *)dst_default_metrics) {
+		fib_info_hold(&fi);
+		klp_shadow_attach(rt, FIB_INFO, &fi, sizeof(fi), GFP_KERNEL)
+	}
+
+	dst_init_metrics(&rt->dst, fi->fib_metrics, true);
+}
+
+The shadow variable can be detached when it's no longer needed:
+
+static void ipv4_dst_destroy(struct dst_entry *dst)
+{
+	struct rtable *rt = (struct rtable *) dst;
+	struct fib_info *shadow_fi;
+
+	shadow_fi = klp_shadow_get(rt, "fi");
+	if (shadow_fi) {
+		klp_shadow_detach(rt, "fi");
+		fib_info_put(shadow_fi);
+	}
+
+
+Other examples: shadow variables can also be used as a simple flag
+indicating that a data structure had been allocated by new, livepatched
+code.  In this case, it doesn't matter what new_data value the shadow
+variable holds, its existence can be keyed off of to handle the data
+structure accordingly.
+
+
+Reference
+==========
+
+* https://github.com/dynup/kpatch
+The livepatch implementation is based on the kpatch version of shadow
+variables.
+
+* http://files.mkgnu.net/files/dynamos/doc/papers/dynamos_eurosys_07.pdf
+Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity
+Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented
+a datatype update technique called "shadow data structures".
diff --git a/include/linux/livepatch.h b/include/linux/livepatch.h
index 194991ef9347..4cf3c285784d 100644
--- a/include/linux/livepatch.h
+++ b/include/linux/livepatch.h
@@ -164,6 +164,14 @@ static inline bool klp_have_reliable_stack(void)
 	       IS_ENABLED(CONFIG_HAVE_RELIABLE_STACKTRACE);
 }
 
+void *klp_shadow_get(void *obj, unsigned long num);
+void *klp_shadow_attach(void *obj, unsigned long num, void *new_data,
+			size_t new_size, gfp_t gfp_flags);
+void *klp_shadow_get_or_attach(void *obj, unsigned long num, void *new_data,
+			       size_t new_size, gfp_t gfp_flags);
+void klp_shadow_detach(void *obj, unsigned long num);
+void klp_shadow_detach_all(unsigned long num);
+
 #else /* !CONFIG_LIVEPATCH */
 
 static inline int klp_module_coming(struct module *mod) { return 0; }
diff --git a/kernel/livepatch/Makefile b/kernel/livepatch/Makefile
index 2b8bdb1925da..b36ceda6488e 100644
--- a/kernel/livepatch/Makefile
+++ b/kernel/livepatch/Makefile
@@ -1,3 +1,3 @@
 obj-$(CONFIG_LIVEPATCH) += livepatch.o
 
-livepatch-objs := core.o patch.o transition.o
+livepatch-objs := core.o patch.o shadow.o transition.o
diff --git a/kernel/livepatch/shadow.c b/kernel/livepatch/shadow.c
new file mode 100644
index 000000000000..d37a61c57e72
--- /dev/null
+++ b/kernel/livepatch/shadow.c
@@ -0,0 +1,257 @@
+/*
+ * shadow.c - Shadow Variables
+ *
+ * Copyright (C) 2014 Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
+ * Copyright (C) 2014 Seth Jennings <sjenning@xxxxxxxxxx>
+ * Copyright (C) 2017 Joe Lawrence <joe.lawrence@xxxxxxxxxx>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, see <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * DOC: Shadow variable API concurrency notes:
+ *
+ * The shadow variable API simply provides a relationship between an
+ * <obj, num> pair and a pointer value.  It is the responsibility of the
+ * caller to provide any mutual exclusion required of the shadow data.
+ *
+ * Once klp_shadow_attach() adds a shadow variable to the
+ * klp_shadow_hash, it is considered live and klp_shadow_get() may
+ * return the shadow variable's new_data pointer.  Therefore,
+ * initialization of shadow new_data should be completed before
+ * attaching the shadow variable.
+ *
+ * Alternatively, the klp_shadow_get_or_attach() call may be used to
+ * safely fetch any existing <obj, num> match, or create a new
+ * <obj, num> shadow variable if none exists.
+ *
+ * If the API is called under a special context (like spinlocks), set
+ * the GFP flags passed to klp_shadow_attach() accordingly.
+ *
+ * The klp_shadow_hash is an RCU-enabled hashtable and should be safe
+ * against concurrent klp_shadow_detach() and klp_shadow_get()
+ * operations.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/hashtable.h>
+#include <linux/slab.h>
+#include <linux/livepatch.h>
+
+static DEFINE_HASHTABLE(klp_shadow_hash, 12);
+static DEFINE_SPINLOCK(klp_shadow_lock);
+
+/**
+ * struct klp_shadow - shadow variable structure
+ * @node:	klp_shadow_hash hash table node
+ * @rcu_head:	RCU is used to safely free this structure
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ * @new_data:	new data area
+ */
+struct klp_shadow {
+	struct hlist_node node;
+	struct rcu_head rcu_head;
+	void *obj;
+	unsigned long num;
+	char new_data[];
+};
+
+/**
+ * shadow_match() - verify a shadow variable matches given <obj, num>
+ * @shadow:	shadow variable to match
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ *
+ * Return: true if the shadow variable matches.
+ */
+static inline bool shadow_match(struct klp_shadow *shadow, void *obj,
+				unsigned long num)
+{
+	return shadow->obj == obj && shadow->num == num;
+}
+
+/**
+ * klp_shadow_get() - retrieve a shadow variable new_data pointer
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ *
+ * Return: a pointer to shadow variable new data
+ */
+void *klp_shadow_get(void *obj, unsigned long num)
+{
+	struct klp_shadow *shadow;
+
+	rcu_read_lock();
+
+	hash_for_each_possible_rcu(klp_shadow_hash, shadow, node,
+				   (unsigned long)obj) {
+
+		if (shadow_match(shadow, obj, num)) {
+			rcu_read_unlock();
+			return shadow->new_data;
+		}
+	}
+
+	rcu_read_unlock();
+
+	return NULL;
+}
+EXPORT_SYMBOL_GPL(klp_shadow_get);
+
+/**
+ * _klp_shadow_attach() - allocate and add a new shadow variable
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ * @new_data:	pointer to new data
+ * @new_size:	size of new data
+ * @gfp_flags:	GFP mask for allocation
+ * @lock:	take klp_shadow_lock during klp_shadow_hash operations
+ *
+ * Note: allocates @new_size space for shadow variable data and copies
+ * @new_size bytes from @new_data into the shadow varaible's own @new_data
+ * space.  If @new_data is NULL, @new_size is still allocated, but no
+ * copy is performed.
+ *
+ * Return: the shadow variable new_data element, NULL on failure.
+ */
+static void *_klp_shadow_attach(void *obj, unsigned long num, void *new_data,
+				size_t new_size, gfp_t gfp_flags,
+				bool lock)
+{
+	struct klp_shadow *shadow;
+	unsigned long flags;
+
+	shadow = kzalloc(new_size + sizeof(*shadow), gfp_flags);
+	if (!shadow)
+		return NULL;
+
+	shadow->obj = obj;
+	shadow->num = num;
+	if (new_data)
+		memcpy(shadow->new_data, new_data, new_size);
+
+	if (lock)
+		spin_lock_irqsave(&klp_shadow_lock, flags);
+	hash_add_rcu(klp_shadow_hash, &shadow->node, (unsigned long)obj);
+	if (lock)
+		spin_unlock_irqrestore(&klp_shadow_lock, flags);
+
+	return shadow->new_data;
+}
+
+/**
+ * klp_shadow_attach() - allocate and add a new shadow variable
+ * @obj:	pointer to original data
+ * @num:	numerical description of new num
+ * @new_data:	pointer to new data
+ * @new_size:	size of new data
+ * @gfp_flags:	GFP mask for allocation
+ *
+ * Return: the shadow variable new_data element, NULL on failure.
+ */
+void *klp_shadow_attach(void *obj, unsigned long num, void *new_data,
+			size_t new_size, gfp_t gfp_flags)
+{
+	return _klp_shadow_attach(obj, num, new_data, new_size,
+				  gfp_flags, true);
+}
+EXPORT_SYMBOL_GPL(klp_shadow_attach);
+
+/**
+ * klp_shadow_get_or_attach() - get existing or attach a new shadow variable
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ * @new_data:	pointer to new data
+ * @new_size:   size of new data
+ * @gfp_flags:	GFP mask used to allocate shadow variable metadata
+ *
+ * Note: if memory allocation is necessary, it will do so under a spinlock,
+ * so @gfp_flags should include GFP_NOWAIT, or GFP_ATOMIC, etc.
+ *
+ * Return: the shadow variable new_data element, NULL on failure.
+ */
+void *klp_shadow_get_or_attach(void *obj, unsigned long num, void *new_data,
+			       size_t new_size, gfp_t gfp_flags)
+{
+	void *nd;
+	unsigned long flags;
+
+	nd = klp_shadow_get(obj, num);
+
+	if (!nd) {
+		spin_lock_irqsave(&klp_shadow_lock, flags);
+		nd = klp_shadow_get(obj, num);
+		if (!nd)
+			nd = _klp_shadow_attach(obj, num, new_data, new_size,
+						gfp_flags, false);
+		spin_unlock_irqrestore(&klp_shadow_lock, flags);
+	}
+
+	return nd;
+
+}
+EXPORT_SYMBOL_GPL(klp_shadow_get_or_attach);
+
+/**
+ * klp_shadow_detach() - detach and free a <obj, num> shadow variable
+ * @obj:	pointer to original data
+ * @num:	numerical description of new data
+ */
+void klp_shadow_detach(void *obj, unsigned long num)
+{
+	struct klp_shadow *shadow;
+	unsigned long flags;
+
+	spin_lock_irqsave(&klp_shadow_lock, flags);
+
+	/* Delete all <obj, num> from hash */
+	hash_for_each_possible(klp_shadow_hash, shadow, node,
+			       (unsigned long)obj) {
+
+		if (shadow_match(shadow, obj, num)) {
+			hash_del_rcu(&shadow->node);
+			kfree_rcu(shadow, rcu_head);
+			break;
+		}
+	}
+
+	spin_unlock_irqrestore(&klp_shadow_lock, flags);
+}
+EXPORT_SYMBOL_GPL(klp_shadow_detach);
+
+/**
+ * klp_shadow_detach_all() - detach all <*, num> shadow variables
+ * @num:	numerical description of new data
+ */
+void klp_shadow_detach_all(unsigned long num)
+{
+	struct klp_shadow *shadow;
+	unsigned long flags;
+	int i;
+
+	spin_lock_irqsave(&klp_shadow_lock, flags);
+
+	/* Delete all <*, num> from hash */
+	hash_for_each(klp_shadow_hash, i, shadow, node) {
+		if (shadow_match(shadow, shadow->obj, num)) {
+			hash_del_rcu(&shadow->node);
+			kfree_rcu(shadow, rcu_head);
+		}
+	}
+
+	spin_unlock_irqrestore(&klp_shadow_lock, flags);
+}
+EXPORT_SYMBOL_GPL(klp_shadow_detach_all);
-- 
1.8.3.1