0001 ================
0002 Shadow Variables
0003 ================
0004
0005 Shadow variables are a simple way for livepatch modules to associate
0006 additional "shadow" data with existing data structures. Shadow data is
0007 allocated separately from parent data structures, which are left
0008 unmodified. The shadow variable API described in this document is used
0009 to allocate/add and remove/free shadow variables to/from their parents.
0010
0011 The implementation introduces a global, in-kernel hashtable that
0012 associates pointers to parent objects and a numeric identifier of the
0013 shadow data. The numeric identifier is a simple enumeration that may be
0014 used to describe shadow variable version, class or type, etc. More
0015 specifically, the parent pointer serves as the hashtable key while the
0016 numeric id subsequently filters hashtable queries. Multiple shadow
0017 variables may attach to the same parent object, but their numeric
0018 identifier distinguishes between them.
0019
0020
0021 1. Brief API summary
0022 ====================
0023
0024 (See the full API usage docbook notes in livepatch/shadow.c.)
0025
0026 A hashtable references all shadow variables. These references are
0027 stored and retrieved through a <obj, id> pair.
0028
0029 * The klp_shadow variable data structure encapsulates both tracking
0030 meta-data and shadow-data:
0031
0032 - meta-data
0033
0034 - obj - pointer to parent object
0035 - id - data identifier
0036
0037 - data[] - storage for shadow data
0038
0039 It is important to note that the klp_shadow_alloc() and
0040 klp_shadow_get_or_alloc() are zeroing the variable by default.
0041 They also allow to call a custom constructor function when a non-zero
0042 value is needed. Callers should provide whatever mutual exclusion
0043 is required.
0044
0045 Note that the constructor is called under klp_shadow_lock spinlock. It allows
0046 to do actions that can be done only once when a new variable is allocated.
0047
0048 * klp_shadow_get() - retrieve a shadow variable data pointer
0049 - search hashtable for <obj, id> pair
0050
0051 * klp_shadow_alloc() - allocate and add a new shadow variable
0052 - search hashtable for <obj, id> pair
0053
0054 - if exists
0055
0056 - WARN and return NULL
0057
0058 - if <obj, id> doesn't already exist
0059
0060 - allocate a new shadow variable
0061 - initialize the variable using a custom constructor and data when provided
0062 - add <obj, id> to the global hashtable
0063
0064 * klp_shadow_get_or_alloc() - get existing or alloc a new shadow variable
0065 - search hashtable for <obj, id> pair
0066
0067 - if exists
0068
0069 - return existing shadow variable
0070
0071 - if <obj, id> doesn't already exist
0072
0073 - allocate a new shadow variable
0074 - initialize the variable using a custom constructor and data when provided
0075 - add <obj, id> pair to the global hashtable
0076
0077 * klp_shadow_free() - detach and free a <obj, id> shadow variable
0078 - find and remove a <obj, id> reference from global hashtable
0079
0080 - if found
0081
0082 - call destructor function if defined
0083 - free shadow variable
0084
0085 * klp_shadow_free_all() - detach and free all <_, id> shadow variables
0086 - find and remove any <_, id> references from global hashtable
0087
0088 - if found
0089
0090 - call destructor function if defined
0091 - free shadow variable
0092
0093
0094 2. Use cases
0095 ============
0096
0097 (See the example shadow variable livepatch modules in samples/livepatch/
0098 for full working demonstrations.)
0099
0100 For the following use-case examples, consider commit 1d147bfa6429
0101 ("mac80211: fix AP powersave TX vs. wakeup race"), which added a
0102 spinlock to net/mac80211/sta_info.h :: struct sta_info. Each use-case
0103 example can be considered a stand-alone livepatch implementation of this
0104 fix.
0105
0106
0107 Matching parent's lifecycle
0108 ---------------------------
0109
0110 If parent data structures are frequently created and destroyed, it may
0111 be easiest to align their shadow variables lifetimes to the same
0112 allocation and release functions. In this case, the parent data
0113 structure is typically allocated, initialized, then registered in some
0114 manner. Shadow variable allocation and setup can then be considered
0115 part of the parent's initialization and should be completed before the
0116 parent "goes live" (ie, any shadow variable get-API requests are made
0117 for this <obj, id> pair.)
0118
0119 For commit 1d147bfa6429, when a parent sta_info structure is allocated,
0120 allocate a shadow copy of the ps_lock pointer, then initialize it::
0121
0122 #define PS_LOCK 1
0123 struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
0124 const u8 *addr, gfp_t gfp)
0125 {
0126 struct sta_info *sta;
0127 spinlock_t *ps_lock;
0128
0129 /* Parent structure is created */
0130 sta = kzalloc(sizeof(*sta) + hw->sta_data_size, gfp);
0131
0132 /* Attach a corresponding shadow variable, then initialize it */
0133 ps_lock = klp_shadow_alloc(sta, PS_LOCK, sizeof(*ps_lock), gfp,
0134 NULL, NULL);
0135 if (!ps_lock)
0136 goto shadow_fail;
0137 spin_lock_init(ps_lock);
0138 ...
0139
0140 When requiring a ps_lock, query the shadow variable API to retrieve one
0141 for a specific struct sta_info:::
0142
0143 void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta)
0144 {
0145 spinlock_t *ps_lock;
0146
0147 /* sync with ieee80211_tx_h_unicast_ps_buf */
0148 ps_lock = klp_shadow_get(sta, PS_LOCK);
0149 if (ps_lock)
0150 spin_lock(ps_lock);
0151 ...
0152
0153 When the parent sta_info structure is freed, first free the shadow
0154 variable::
0155
0156 void sta_info_free(struct ieee80211_local *local, struct sta_info *sta)
0157 {
0158 klp_shadow_free(sta, PS_LOCK, NULL);
0159 kfree(sta);
0160 ...
0161
0162
0163 In-flight parent objects
0164 ------------------------
0165
0166 Sometimes it may not be convenient or possible to allocate shadow
0167 variables alongside their parent objects. Or a livepatch fix may
0168 require shadow variables for only a subset of parent object instances.
0169 In these cases, the klp_shadow_get_or_alloc() call can be used to attach
0170 shadow variables to parents already in-flight.
0171
0172 For commit 1d147bfa6429, a good spot to allocate a shadow spinlock is
0173 inside ieee80211_sta_ps_deliver_wakeup()::
0174
0175 int ps_lock_shadow_ctor(void *obj, void *shadow_data, void *ctor_data)
0176 {
0177 spinlock_t *lock = shadow_data;
0178
0179 spin_lock_init(lock);
0180 return 0;
0181 }
0182
0183 #define PS_LOCK 1
0184 void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta)
0185 {
0186 spinlock_t *ps_lock;
0187
0188 /* sync with ieee80211_tx_h_unicast_ps_buf */
0189 ps_lock = klp_shadow_get_or_alloc(sta, PS_LOCK,
0190 sizeof(*ps_lock), GFP_ATOMIC,
0191 ps_lock_shadow_ctor, NULL);
0192
0193 if (ps_lock)
0194 spin_lock(ps_lock);
0195 ...
0196
0197 This usage will create a shadow variable, only if needed, otherwise it
0198 will use one that was already created for this <obj, id> pair.
0199
0200 Like the previous use-case, the shadow spinlock needs to be cleaned up.
0201 A shadow variable can be freed just before its parent object is freed,
0202 or even when the shadow variable itself is no longer required.
0203
0204
0205 Other use-cases
0206 ---------------
0207
0208 Shadow variables can also be used as a flag indicating that a data
0209 structure was allocated by new, livepatched code. In this case, it
0210 doesn't matter what data value the shadow variable holds, its existence
0211 suggests how to handle the parent object.
0212
0213
0214 3. References
0215 =============
0216
0217 * https://github.com/dynup/kpatch
0218
0219 The livepatch implementation is based on the kpatch version of shadow
0220 variables.
0221
0222 * http://files.mkgnu.net/files/dynamos/doc/papers/dynamos_eurosys_07.pdf
0223
0224 Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity
0225 Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented
0226 a datatype update technique called "shadow data structures".
