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