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 184 #ifndef _SYS_EXISLOCK_H_ 185 #define _SYS_EXISLOCK_H_ 186 187 #include <sys/globaldata.h> 188 #include <machine/thread.h> 189 190 struct thread; 191 192 struct exislock { 193 long pseudo_ticks; 194 }; 195 typedef struct exislock exislock_t; 196 197 typedef enum exis_state { 198 EXIS_TERMINATE, 199 EXIS_NOTCACHED, 200 EXIS_CACHED, 201 EXIS_LIVE 202 } exis_state_t; 203 204 extern long pseudo_ticks; 205 206 /* 207 * Initialize the structure 208 */ 209 static __inline void 210 exis_init(exislock_t *xlk) 211 { 212 xlk->pseudo_ticks = 0; 213 } 214 215 /* 216 * pcpu exis lock API. Enter and and exit a type-safe critical section. 217 */ 218 static __inline void 219 exis_hold_gd(globaldata_t gd) 220 { 221 ++gd->gd_exislockcnt; 222 } 223 224 static __inline void 225 exis_drop_gd(globaldata_t gd) 226 { 227 if (--gd->gd_exislockcnt == 0) 228 gd->gd_exisarmed = 1; 229 } 230 231 static __inline void 232 exis_hold(void) 233 { 234 exis_hold_gd(mycpu); 235 } 236 237 static __inline void 238 exis_drop(void) 239 { 240 exis_drop_gd(mycpu); 241 } 242 243 /* 244 * poll whether the object is usable or not. A value >= 0 indicates that 245 * the (possibly cached) object is usable. 246 * 247 * This call returns the approximate number of pseudo_ticks remaining until 248 * the object becomes unusable, +/- one. 249 * 250 * The actual value returns is either >= 0, or a negative number. Caller 251 * should refrain from trying to interpret values >= 0 other than the fact 252 * that they are >= 0. 253 * 254 * Negative numbers indicate the number of pseudo_ticks which have occurred 255 * since the object became unusable. Various negative values trigger different 256 */ 257 static __inline long 258 exis_poll(exislock_t *xlk) 259 { 260 long val = xlk->pseudo_ticks; 261 262 cpu_ccfence(); 263 if (val == 0) 264 return val; 265 return (pseudo_ticks - val); 266 } 267 268 /* 269 * Return the current state. Note that the NOTCACHED state persists for 270 * two pseudo_ticks. This is done because the global pseudo_ticks counter 271 * can concurrently increment by 1 (but no more than 1) during a type-safe 272 * critical section. 273 * 274 * The state can transition even while holding a type-safe critical section, 275 * but sequencing is designed such that this does not cause any problems. 276 */ 277 static __inline int 278 exis_state(exislock_t *xlk) 279 { 280 long val = xlk->pseudo_ticks; 281 282 cpu_ccfence(); 283 if (val == 0) 284 return EXIS_LIVE; 285 val = pseudo_ticks - val; 286 if (val >= 0) 287 return EXIS_CACHED; 288 if (val >= -2) 289 return EXIS_NOTCACHED; 290 return EXIS_TERMINATE; 291 } 292 293 /* 294 * Returns non-zero if the structure is usable (either LIVE or CACHED). 295 * 296 * WARNING! The structure is not considered to be usable if it is in 297 * an UNCACHED state, but if it is CACHED and transitions to 298 * UNCACHED during a type-safe critical section it does remain 299 * usable for the duration of that type-safe critical section. 300 */ 301 static __inline int 302 exis_usable(exislock_t *xlk) 303 { 304 return (exis_poll(xlk) >= 0); 305 } 306 307 /* 308 * If the structure is in a LIVE or CACHED state, or if it was CACHED and 309 * concurrently transitioned to NOTCACHED in the same type-safe critical 310 * section, the state will be reset to a CACHED(n) state and non-zero is 311 * returned. 312 * 313 * Otherwise 0 is returned and no action is taken. 314 */ 315 static __inline int 316 exis_cache(exislock_t *xlk, long n) 317 { 318 long val = xlk->pseudo_ticks; 319 long pticks = pseudo_ticks; 320 321 cpu_ccfence(); 322 if (val) 323 val = val - pticks; 324 if (val >= -1) { 325 /* 326 * avoid cache line ping-pong 327 */ 328 pticks += n + 1; 329 if (xlk->pseudo_ticks != pticks) { 330 cpu_ccfence(); 331 xlk->pseudo_ticks = pticks; 332 } 333 return 1; 334 } 335 return 0; 336 } 337 338 /* 339 * Termination sequencing. 340 * 341 * The structure is placed in a CACHED(0) state if LIVE or CACHED. 342 * The NOTCACHED state should not be acted upon by the caller until 343 * and unless it transitions to TERMINATE. 344 * 345 * Upon returning EXIS_TERMINATE, the structure is returned to a 346 * NOTCACHED state and another 1-2 pseudo ticks will pass until it goes 347 * back to EXIS_TERMINATE (if needed by the caller). Once the caller 348 * is fully satisfied, it may repurpose or destroy the structure. 349 * 350 * Caller should hold a strong interlock on the structure in addition 351 * to being in a type-safe critical section. 352 */ 353 static __inline exis_state_t 354 exis_terminate(exislock_t *xlk) 355 { 356 exis_state_t state; 357 358 state = exis_state(xlk); 359 switch(state) { 360 case EXIS_TERMINATE: 361 /* 362 * Set to NOTCACHED state and return EXIS_TERMINATE. 363 * due to pseudo_ticks races, the NOTCACHED state will 364 * persist for 1-2 pseudo ticks. 365 */ 366 xlk->pseudo_ticks = pseudo_ticks - 1; 367 state = EXIS_TERMINATE; 368 break; 369 case EXIS_NOTCACHED: 370 break; 371 case EXIS_CACHED: 372 case EXIS_LIVE: 373 xlk->pseudo_ticks = pseudo_ticks; 374 break; 375 } 376 return state; 377 } 378 379 #endif /* !_SYS_EXISLOCK_H_ */ 380