1 /* 2 * Copyright (c) 2020 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 /* 35 * Existential Lock implementation 36 * 37 * This implements an API which allows consumers to safely manage the 38 * caching, destruction, repurposing, or reuse of system structures against 39 * concurrent accessors on other cpus without the use of locks or cache 40 * line bounces in the critical path. 41 * 42 * An accessor wraps the critical code with an exis_hold() and exis_drop() 43 * pair. This increments a contention-free per-cpu ref-count which prevents 44 * the pseudo_ticks global from incrementing more than once. The accessor 45 * can block for short periods of time inside the code block (but should not 46 * block indefinitely as overlapping accessors may then prevent pseudo_ticks 47 * from ever incrementing!). 48 * 49 * The subsystem which intends to destroy, repurpose, or reuse the structure 50 * first unlinks the structure from whatever data structures accessors use 51 * to find it, and then issues exis_terminate() on the exislock for the 52 * structure. The subsystem can then call exis_poll() on the exislock to 53 * determine when it is safe to destroy, repurpose, or reuse the structure. 54 * This will occur EXIS_THRESH pseudo_ticks after the exis_terminate() call. 55 */ 56 57 /* 58 * API 59 * 60 * exis_hold() 61 * exis_drop() 62 * 63 * Wrap type-safe critical code, preventing the global pseudo_ticks 64 * counter from incrementing more than once. The counter may still 65 * increment zero or one time. 66 * 67 * The code may block, but should not block forever since it will 68 * prevent state transitions for the type-safe API across the entire 69 * system. 70 * 71 * All other API functions (except exis_init() for intitializing a 72 * new structure from scratch) should only be called while a type-safe 73 * critical section is held. 74 * 75 * exis_init() 76 * 77 * Unconditionally initialize the exis structure, placing it in a 78 * EXIS_LIVE state. 79 * 80 * exis_poll() 81 * 82 * Return the pseudo_ticks delta relative to an exis structure. A 83 * value >= 0 indicates that the structure is LIVE or CACHED. A negative 84 * value indicates that the structure is not usable. Values 85 * should not generally be interpreted beyond this. 86 * 87 * exis_state() 88 * 89 * Returns the current EXIS_* state of the structure. EXIS_TERMINATE, 90 * EXIS_NOTCACHED, EXIS_CACHED, or EXIS_LIVE. This macro has a bit of 91 * complexity to it and is not usually called in the critical path. 92 * Instead, exis_isusable() is typically called. 93 * 94 * exis_usable() 95 * 96 * Returns non-zero if the exis structure is usable, meaning that it 97 * is in a LIVE or CACHED state. 98 * 99 * exis_cache(N) 100 * 101 * Transitions an exis structure from LIVE or CACHED to CACHED and 102 * refreshes the time the structure will remain cached to approximately 103 * (N) pseudo_ticks. Returns TRUE in this case. 104 * 105 * A structure can transition from CACHED to NOTCACHED while a 106 * type-safe critical section is held, due to the possibility of 107 * pseudo_ticks incrementing once. To handle this case, any 108 * structure in a NOTCACHED state will be changed backed to a 109 * CACHED state for approximtely (N) pseudo_ticks and TRUE will be 110 * returned. 111 * 112 * WARNING! It is extremely important that exis_cache(N) not be called 113 * on a structure that was polled to be in a NOTCACHED state. The only 114 * case where this is allowed is if the structure was originally found 115 * to be in a CACHED state and then concurrently transitioned to 116 * NOTCACHED. THAT race is ok, but an initial NOTCACHED state is not 117 * ok. The reason is that the NOTCACHED state is used to sequence 118 * multiple TERMINATE stages (if the caller desires this). 119 * 120 * A structure in any other state will not be modified and FALSE will 121 * be returned. 122 * 123 * The value (0) can be passed to cause the structure to enter into 124 * a CACHED state with the least timeout. 125 * 126 * exis_terminate() 127 * 128 * If the structure is in a LIVE state the structure will be set to 129 * a CACHED(0) state and EXIS_LIVE will be returned. The caller 130 * can return the structure to a LIVE state if desired but should 131 * otherwise take no action. 132 * 133 * If the structure is in a CACHED state the structure will be set to 134 * a CACHED(0) state and EXIS_CACHED will be returned. The caller 135 * can return the structure to a LIVE or CACHED state if desired 136 * but should otherwise take no action. 137 * 138 * A structure will be in a NOTCACHED state for 2 pseudo ticks after 139 * leaving the CACHED state. EXIS_NOTCACHED is returned and the caller 140 * should not take any action on the structure. 141 * 142 * TERMINATION SEQUENCING 143 * 144 * After 1-2 ticks in the NOTCACHED state, the structure enters the 145 * EXIS_TERMINATE state. Note that it may still be connected to 146 * system data structures at this time and full concurrent access 147 * requires some termination staging. 148 * 149 * exis_terminate() will return EXIS_TERMINATE but also set the exis 150 * structure back to a NOTCACHED state for 1-2 ticks. The caller 151 * typically must hold a strong lock on the structure and/or related 152 * data structures to properly terminate it. 153 * 154 * --- For the first TERMINATE, the caller removes the object from 155 * system data structures. It is important that the caller 156 * NOT DESTROY the type-safe nature of the object at this time. 157 * 158 * --- For the second TERMINATE, the caller may destroy the object. 159 * The caller usually distinguishes the two states with a flag 160 * or checking pointer fields or whatnot. 161 * 162 * --- Additional TERMINATE states may be sequenced if necessary, there 163 * is no limit. 164 * 165 * REACTIVATION SEQUENCING 166 * 167 * Structures can remain in memory, unaccessed, for long periods of time. 168 * This can cause the structure to wind up in an EXIS_TERMINATE state. 169 * The result is that stronger locks will be needed when looking up the 170 * structure and the code doing this can then re-activate the EXIS state 171 * by issuing exis_init(), and then re-cache (if desired) it via 172 * exis_cache(). 173 * 174 * Repeated lookups of the same structure are likely to remain cached 175 * for the caching period (N ticks, via the API) before having to refresh 176 * the structure again. Or indefinitely if the exis lock is in the 177 * LIVE state. 178 * 179 * Thus an EXIS_TERMIANTE state does *NOT* necessarily mean that the 180 * caller actually intends to terminate the structure, only that stronger 181 * locking will be required to return it to its fast-access state. 182 */ 183 #include <sys/lock.h> 184 #include <machine/cpumask.h> 185 186 struct thread; 187 188 struct exislock { 189 long pseudo_ticks; 190 }; 191 typedef struct exislock exislock_t; 192 193 typedef enum exis_state { 194 EXIS_TERMINATE, 195 EXIS_NOTCACHED, 196 EXIS_CACHED, 197 EXIS_LIVE 198 } exis_state_t; 199 200 extern long pseudo_ticks; 201 202 /* 203 * Initialize the structure 204 */ 205 static __inline void 206 exis_init(exislock_t *xlk) 207 { 208 xlk->pseudo_ticks = 0; 209 } 210 211 /* 212 * pcpu exis lock API. Enter and and exit a type-safe critical section. 213 */ 214 static __inline void 215 exis_hold_gd(globaldata_t gd) 216 { 217 ++gd->gd_exislockcnt; 218 } 219 220 static __inline void 221 exis_drop_gd(globaldata_t gd) 222 { 223 if (--gd->gd_exislockcnt == 0) 224 gd->gd_exisarmed = 1; 225 } 226 227 static __inline void 228 exis_hold(void) 229 { 230 exis_hold_gd(mycpu); 231 } 232 233 static __inline void 234 exis_drop(void) 235 { 236 exis_drop_gd(mycpu); 237 } 238 239 /* 240 * poll whether the object is usable or not. A value >= 0 indicates that 241 * the (possibly cached) object is usable. 242 * 243 * This call returns the approximate number of pseudo_ticks remaining until 244 * the object becomes unusable, +/- one. 245 * 246 * The actual value returns is either >= 0, or a negative number. Caller 247 * should refrain from trying to interpret values >= 0 other than the fact 248 * that they are >= 0. 249 * 250 * Negative numbers indicate the number of pseudo_ticks which have occurred 251 * since the object became unusable. Various negative values trigger different 252 */ 253 static __inline long 254 exis_poll(exislock_t *xlk) 255 { 256 long val = xlk->pseudo_ticks; 257 258 cpu_ccfence(); 259 if (val == 0) 260 return val; 261 return (pseudo_ticks - val); 262 } 263 264 /* 265 * Return the current state. Note that the NOTCACHED state persists for 266 * two pseudo_ticks. This is done because the global pseudo_ticks counter 267 * can concurrently increment by 1 (but no more than 1) during a type-safe 268 * critical section. 269 * 270 * The state can transition even while holding a type-safe critical section, 271 * but sequencing is designed such that this does not cause any problems. 272 */ 273 static __inline int 274 exis_state(exislock_t *xlk) 275 { 276 long val = xlk->pseudo_ticks; 277 278 cpu_ccfence(); 279 if (val == 0) 280 return EXIS_LIVE; 281 val = pseudo_ticks - val; 282 if (val >= 0) 283 return EXIS_CACHED; 284 if (val >= -2) 285 return EXIS_NOTCACHED; 286 return EXIS_TERMINATE; 287 } 288 289 /* 290 * Returns non-zero if the structure is usable (either LIVE or CACHED). 291 * 292 * WARNING! The structure is not considered to be usable if it is in 293 * an UNCACHED state, but if it is CACHED and transitions to 294 * UNCACHED during a type-safe critical section it does remain 295 * usable for the duration of that type-safe critical section. 296 */ 297 static __inline int 298 exis_usable(exislock_t *xlk) 299 { 300 return (exis_poll(xlk) >= 0); 301 } 302 303 /* 304 * If the structure is in a LIVE or CACHED state, or if it was CACHED and 305 * concurrently transitioned to NOTCACHED in the same type-safe critical 306 * section, the state will be reset to a CACHED(n) state and non-zero is 307 * returned. 308 * 309 * Otherwise 0 is returned and no action is taken. 310 */ 311 static __inline int 312 exis_cache(exislock_t *xlk, long n) 313 { 314 long val = xlk->pseudo_ticks; 315 long pticks = pseudo_ticks; 316 317 cpu_ccfence(); 318 if (val) 319 val = val - pticks; 320 if (val >= -1) { 321 /* 322 * avoid cache line ping-pong 323 */ 324 pticks += n + 1; 325 if (xlk->pseudo_ticks != pticks) { 326 cpu_ccfence(); 327 xlk->pseudo_ticks = pticks; 328 } 329 return 1; 330 } 331 return 0; 332 } 333 334 /* 335 * Termination sequencing. 336 * 337 * The structure is placed in a CACHED(0) state if LIVE or CACHED. 338 * The NOTCACHED state should not be acted upon by the caller until 339 * and unless it transitions to TERMINATE. 340 * 341 * Upon returning EXIS_TERMINATE, the structure is returned to a 342 * NOTCACHED state and another 1-2 pseudo ticks will pass until it goes 343 * back to EXIS_TERMINATE (if needed by the caller). Once the caller 344 * is fully satisfied, it may repurpose or destroy the structure. 345 * 346 * Caller should hold a strong interlock on the structure in addition 347 * to being in a type-safe critical section. 348 */ 349 static __inline exis_state_t 350 exis_terminate(exislock_t *xlk) 351 { 352 exis_state_t state; 353 354 state = exis_state(xlk); 355 switch(state) { 356 case EXIS_TERMINATE: 357 /* 358 * Set to NOTCACHED state and return EXIS_TERMINATE. 359 * due to pseudo_ticks races, the NOTCACHED state will 360 * persist for 1-2 pseudo ticks. 361 */ 362 xlk->pseudo_ticks = pseudo_ticks - 1; 363 state = EXIS_TERMINATE; 364 break; 365 case EXIS_NOTCACHED: 366 break; 367 case EXIS_CACHED: 368 case EXIS_LIVE: 369 xlk->pseudo_ticks = pseudo_ticks; 370 break; 371 } 372 return state; 373 } 374