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