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