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