1================
  2Shadow Variables
  3================
  4
  5Shadow variables are a simple way for livepatch modules to associate
  6additional "shadow" data with existing data structures.  Shadow data is
  7allocated separately from parent data structures, which are left
  8unmodified.  The shadow variable API described in this document is used
  9to allocate/add and remove/free shadow variables to/from their parents.
 10
 11The implementation introduces a global, in-kernel hashtable that
 12associates pointers to parent objects and a numeric identifier of the
 13shadow data.  The numeric identifier is a simple enumeration that may be
 14used to describe shadow variable version, class or type, etc.  More
 15specifically, the parent pointer serves as the hashtable key while the
 16numeric id subsequently filters hashtable queries.  Multiple shadow
 17variables may attach to the same parent object, but their numeric
 18identifier distinguishes between them.
 19
 20
 211. Brief API summary
 22====================
 23
 24(See the full API usage docbook notes in livepatch/shadow.c.)
 25
 26A hashtable references all shadow variables.  These references are
 27stored and retrieved through a <obj, id> pair.
 28
 29* The klp_shadow variable data structure encapsulates both tracking
 30meta-data and shadow-data:
 31  - meta-data
 32    - obj - pointer to parent object
 33    - id - data identifier
 34  - data[] - storage for shadow data
 35
 36It is important to note that the klp_shadow_alloc() and
 37klp_shadow_get_or_alloc() are zeroing the variable by default.
 38They also allow to call a custom constructor function when a non-zero
 39value is needed. Callers should provide whatever mutual exclusion
 40is required.
 41
 42Note that the constructor is called under klp_shadow_lock spinlock. It allows
 43to do actions that can be done only once when a new variable is allocated.
 44
 45* klp_shadow_get() - retrieve a shadow variable data pointer
 46  - search hashtable for <obj, id> pair
 47
 48* klp_shadow_alloc() - allocate and add a new shadow variable
 49  - search hashtable for <obj, id> pair
 50  - if exists
 51    - WARN and return NULL
 52  - if <obj, id> doesn't already exist
 53    - allocate a new shadow variable
 54    - initialize the variable using a custom constructor and data when provided
 55    - add <obj, id> to the global hashtable
 56
 57* klp_shadow_get_or_alloc() - get existing or alloc a new shadow variable
 58  - search hashtable for <obj, id> pair
 59  - if exists
 60    - return existing shadow variable
 61  - if <obj, id> doesn't already exist
 62    - allocate a new shadow variable
 63    - initialize the variable using a custom constructor and data when provided
 64    - add <obj, id> pair to the global hashtable
 65
 66* klp_shadow_free() - detach and free a <obj, id> shadow variable
 67  - find and remove a <obj, id> reference from global hashtable
 68    - if found
 69      - call destructor function if defined
 70      - free shadow variable
 71
 72* klp_shadow_free_all() - detach and free all <*, id> shadow variables
 73  - find and remove any <*, id> references from global hashtable
 74    - if found
 75      - call destructor function if defined
 76      - free shadow variable
 77
 78
 792. Use cases
 80============
 81
 82(See the example shadow variable livepatch modules in samples/livepatch/
 83for full working demonstrations.)
 84
 85For the following use-case examples, consider commit 1d147bfa6429
 86("mac80211: fix AP powersave TX vs.  wakeup race"), which added a
 87spinlock to net/mac80211/sta_info.h :: struct sta_info.  Each use-case
 88example can be considered a stand-alone livepatch implementation of this
 89fix.
 90
 91
 92Matching parent's lifecycle
 93---------------------------
 94
 95If parent data structures are frequently created and destroyed, it may
 96be easiest to align their shadow variables lifetimes to the same
 97allocation and release functions.  In this case, the parent data
 98structure is typically allocated, initialized, then registered in some
 99manner.  Shadow variable allocation and setup can then be considered
100part of the parent's initialization and should be completed before the
101parent "goes live" (ie, any shadow variable get-API requests are made
102for this <obj, id> pair.)
103
104For commit 1d147bfa6429, when a parent sta_info structure is allocated,
105allocate a shadow copy of the ps_lock pointer, then initialize it:
106
107#define PS_LOCK 1
108struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
109				const u8 *addr, gfp_t gfp)
110{
111	struct sta_info *sta;
112	spinlock_t *ps_lock;
113
114	/* Parent structure is created */
115	sta = kzalloc(sizeof(*sta) + hw->sta_data_size, gfp);
116
117	/* Attach a corresponding shadow variable, then initialize it */
118	ps_lock = klp_shadow_alloc(sta, PS_LOCK, sizeof(*ps_lock), gfp,
119				   NULL, NULL);
120	if (!ps_lock)
121		goto shadow_fail;
122	spin_lock_init(ps_lock);
123	...
124
125When requiring a ps_lock, query the shadow variable API to retrieve one
126for a specific struct sta_info:
127
128void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta)
129{
130	spinlock_t *ps_lock;
131
132	/* sync with ieee80211_tx_h_unicast_ps_buf */
133	ps_lock = klp_shadow_get(sta, PS_LOCK);
134	if (ps_lock)
135		spin_lock(ps_lock);
136	...
137
138When the parent sta_info structure is freed, first free the shadow
139variable:
140
141void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
142{
143	klp_shadow_free(sta, PS_LOCK, NULL);
144	kfree(sta);
145	...
146
147
148In-flight parent objects
149------------------------
150
151Sometimes it may not be convenient or possible to allocate shadow
152variables alongside their parent objects.  Or a livepatch fix may
153require shadow varibles to only a subset of parent object instances.  In
154these cases, the klp_shadow_get_or_alloc() call can be used to attach
155shadow variables to parents already in-flight.
156
157For commit 1d147bfa6429, a good spot to allocate a shadow spinlock is
158inside ieee80211_sta_ps_deliver_wakeup():
159
160int ps_lock_shadow_ctor(void *obj, void *shadow_data, void *ctor_data)
161{
162	spinlock_t *lock = shadow_data;
163
164	spin_lock_init(lock);
165	return 0;
166}
167
168#define PS_LOCK 1
169void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta)
170{
171	spinlock_t *ps_lock;
172
173	/* sync with ieee80211_tx_h_unicast_ps_buf */
174	ps_lock = klp_shadow_get_or_alloc(sta, PS_LOCK,
175			sizeof(*ps_lock), GFP_ATOMIC,
176			ps_lock_shadow_ctor, NULL);
177
178	if (ps_lock)
179		spin_lock(ps_lock);
180	...
181
182This usage will create a shadow variable, only if needed, otherwise it
183will use one that was already created for this <obj, id> pair.
184
185Like the previous use-case, the shadow spinlock needs to be cleaned up.
186A shadow variable can be freed just before its parent object is freed,
187or even when the shadow variable itself is no longer required.
188
189
190Other use-cases
191---------------
192
193Shadow variables can also be used as a flag indicating that a data
194structure was allocated by new, livepatched code.  In this case, it
195doesn't matter what data value the shadow variable holds, its existence
196suggests how to handle the parent object.
197
198
1993. References
200=============
201
202* https://github.com/dynup/kpatch
203The livepatch implementation is based on the kpatch version of shadow
204variables.
205
206* http://files.mkgnu.net/files/dynamos/doc/papers/dynamos_eurosys_07.pdf
207Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity
208Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented
209a datatype update technique called "shadow data structures".