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 | |
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 | |
e91c2518 PM |
37 | klp_shadow_get_or_alloc() are zeroing the variable by default. |
38 | They also allow to call a custom constructor function when a non-zero | |
39 | value is needed. Callers should provide whatever mutual exclusion | |
40 | is required. | |
41 | ||
42 | Note that the constructor is called under klp_shadow_lock spinlock. It allows | |
43 | to do actions that can be done only once when a new variable is allocated. | |
439e7271 JL |
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 | |
e91c2518 | 54 | - initialize the variable using a custom constructor and data when provided |
439e7271 JL |
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 | |
e91c2518 | 63 | - initialize the variable using a custom constructor and data when provided |
439e7271 JL |
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 | |
3b2c77d0 PM |
68 | - if found |
69 | - call destructor function if defined | |
70 | - free shadow variable | |
439e7271 JL |
71 | |
72 | * klp_shadow_free_all() - detach and free all <*, id> shadow variables | |
73 | - find and remove any <*, id> references from global hashtable | |
3b2c77d0 PM |
74 | - if found |
75 | - call destructor function if defined | |
76 | - free shadow variable | |
439e7271 JL |
77 | |
78 | ||
79 | 2. Use cases | |
80 | ============ | |
81 | ||
82 | (See the example shadow variable livepatch modules in samples/livepatch/ | |
83 | for full working demonstrations.) | |
84 | ||
85 | For the following use-case examples, consider commit 1d147bfa6429 | |
86 | ("mac80211: fix AP powersave TX vs. wakeup race"), which added a | |
87 | spinlock to net/mac80211/sta_info.h :: struct sta_info. Each use-case | |
88 | example can be considered a stand-alone livepatch implementation of this | |
89 | fix. | |
90 | ||
91 | ||
92 | Matching parent's lifecycle | |
93 | --------------------------- | |
94 | ||
95 | If parent data structures are frequently created and destroyed, it may | |
96 | be easiest to align their shadow variables lifetimes to the same | |
97 | allocation and release functions. In this case, the parent data | |
98 | structure is typically allocated, initialized, then registered in some | |
99 | manner. Shadow variable allocation and setup can then be considered | |
100 | part of the parent's initialization and should be completed before the | |
101 | parent "goes live" (ie, any shadow variable get-API requests are made | |
102 | for this <obj, id> pair.) | |
103 | ||
104 | For commit 1d147bfa6429, when a parent sta_info structure is allocated, | |
105 | allocate a shadow copy of the ps_lock pointer, then initialize it: | |
106 | ||
107 | #define PS_LOCK 1 | |
108 | struct 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 */ | |
e91c2518 PM |
118 | ps_lock = klp_shadow_alloc(sta, PS_LOCK, sizeof(*ps_lock), gfp, |
119 | NULL, NULL); | |
439e7271 JL |
120 | if (!ps_lock) |
121 | goto shadow_fail; | |
122 | spin_lock_init(ps_lock); | |
123 | ... | |
124 | ||
125 | When requiring a ps_lock, query the shadow variable API to retrieve one | |
126 | for a specific struct sta_info: | |
127 | ||
128 | void 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 | ||
138 | When the parent sta_info structure is freed, first free the shadow | |
139 | variable: | |
140 | ||
141 | void sta_info_free(struct ieee80211_local *local, struct sta_info *sta) | |
142 | { | |
3b2c77d0 | 143 | klp_shadow_free(sta, PS_LOCK, NULL); |
439e7271 JL |
144 | kfree(sta); |
145 | ... | |
146 | ||
147 | ||
148 | In-flight parent objects | |
149 | ------------------------ | |
150 | ||
151 | Sometimes it may not be convenient or possible to allocate shadow | |
152 | variables alongside their parent objects. Or a livepatch fix may | |
153 | require shadow varibles to only a subset of parent object instances. In | |
154 | these cases, the klp_shadow_get_or_alloc() call can be used to attach | |
155 | shadow variables to parents already in-flight. | |
156 | ||
157 | For commit 1d147bfa6429, a good spot to allocate a shadow spinlock is | |
158 | inside ieee80211_sta_ps_deliver_wakeup(): | |
159 | ||
e91c2518 PM |
160 | int 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 | ||
439e7271 JL |
168 | #define PS_LOCK 1 |
169 | void ieee80211_sta_ps_deliver_wakeup(struct sta_info *sta) | |
170 | { | |
439e7271 JL |
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, | |
e91c2518 PM |
175 | sizeof(*ps_lock), GFP_ATOMIC, |
176 | ps_lock_shadow_ctor, NULL); | |
177 | ||
439e7271 JL |
178 | if (ps_lock) |
179 | spin_lock(ps_lock); | |
180 | ... | |
181 | ||
182 | This usage will create a shadow variable, only if needed, otherwise it | |
183 | will use one that was already created for this <obj, id> pair. | |
184 | ||
185 | Like the previous use-case, the shadow spinlock needs to be cleaned up. | |
186 | A shadow variable can be freed just before its parent object is freed, | |
187 | or even when the shadow variable itself is no longer required. | |
188 | ||
189 | ||
190 | Other use-cases | |
191 | --------------- | |
192 | ||
193 | Shadow variables can also be used as a flag indicating that a data | |
194 | structure was allocated by new, livepatched code. In this case, it | |
195 | doesn't matter what data value the shadow variable holds, its existence | |
196 | suggests how to handle the parent object. | |
197 | ||
198 | ||
199 | 3. References | |
200 | ============= | |
201 | ||
202 | * https://github.com/dynup/kpatch | |
203 | The livepatch implementation is based on the kpatch version of shadow | |
204 | variables. | |
205 | ||
206 | * http://files.mkgnu.net/files/dynamos/doc/papers/dynamos_eurosys_07.pdf | |
207 | Dynamic and Adaptive Updates of Non-Quiescent Subsystems in Commodity | |
208 | Operating System Kernels (Kritis Makris, Kyung Dong Ryu 2007) presented | |
209 | a datatype update technique called "shadow data structures". |