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 (see sys/exislock2.h) 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. -1 indicates 85 * NOTCACHED and <= -2 indicates TERMINATE (freeable). 86 * 87 * Values should not generally be interpreted beyond this. Instead, 88 * use exis_state(), exis_usable(), and exis_freeable(). 89 * 90 * exis_state() 91 * 92 * Returns the current EXIS_* state of the structure. EXIS_TERMINATE, 93 * EXIS_NOTCACHED, EXIS_CACHED, or EXIS_LIVE. This macro has a bit of 94 * complexity to it and is not usually called in the critical path. 95 * Instead, exis_isusable() is typically called. 96 * 97 * exis_usable() 98 * 99 * Returns non-zero if the exis structure is usable, meaning that it 100 * is in a LIVE or CACHED state (>= 0). 101 * 102 * exis_freeable() 103 * 104 * Returns non-zero if the exis structure is usable, meaning that it 105 * is in a TERMINATE state (<= -2). 106 * 107 * exis_cache(N) 108 * 109 * Transitions an exis structure from LIVE or CACHED to CACHED and 110 * refreshes the time the structure will remain cached to approximately 111 * (N) pseudo_ticks. Returns TRUE in this case. 112 * 113 * A structure can transition from CACHED to NOTCACHED while a 114 * type-safe critical section is held, due to the possibility of 115 * pseudo_ticks incrementing once. To handle this case, any 116 * structure in a NOTCACHED state will be changed backed to a 117 * CACHED state for approximtely (N) pseudo_ticks and TRUE will be 118 * returned. 119 * 120 * WARNING! It is extremely important that exis_cache(N) not be called 121 * on a structure that was polled to be in a NOTCACHED state. The only 122 * case where this is allowed is if the structure was originally found 123 * to be in a CACHED state and then concurrently transitioned to 124 * NOTCACHED. THAT race is ok, but an initial NOTCACHED state is not 125 * ok. The reason is that the NOTCACHED state is used to sequence 126 * multiple TERMINATE stages (if the caller desires this). 127 * 128 * A structure in any other state will not be modified and FALSE will 129 * be returned. 130 * 131 * The value (0) can be passed to cause the structure to enter into 132 * a CACHED state with the least timeout. 133 * 134 * exis_terminate() 135 * 136 * If the structure is in a LIVE state the structure will be set to 137 * a CACHED(0) state and EXIS_LIVE will be returned. The caller 138 * can return the structure to a LIVE state if desired but should 139 * otherwise take no action. 140 * 141 * If the structure is in a CACHED state the structure will be set to 142 * a CACHED(0) state and EXIS_CACHED will be returned. The caller 143 * can return the structure to a LIVE or CACHED state if desired 144 * but should otherwise take no action. 145 * 146 * A structure will be in a NOTCACHED state for 2 pseudo ticks after 147 * leaving the CACHED state. EXIS_NOTCACHED is returned and the caller 148 * should not take any action on the structure. 149 * 150 * TERMINATION SEQUENCING 151 * 152 * After 1-2 ticks in the NOTCACHED state, the structure enters the 153 * EXIS_TERMINATE state. Note that it may still be connected to 154 * system data structures at this time and full concurrent access 155 * requires some termination staging. 156 * 157 * exis_terminate() will return EXIS_TERMINATE but also set the exis 158 * structure back to a NOTCACHED state for 1-2 ticks. The caller 159 * typically must hold a strong lock on the structure and/or related 160 * data structures to properly terminate it. 161 * 162 * --- For the first TERMINATE, the caller removes the object from 163 * system data structures. It is important that the caller 164 * NOT DESTROY the type-safe nature of the object at this time. 165 * 166 * --- For the second TERMINATE, the caller may destroy the object. 167 * The caller usually distinguishes the two states with a flag 168 * or checking pointer fields or whatnot. 169 * 170 * --- Additional TERMINATE states may be sequenced if necessary, there 171 * is no limit. 172 * 173 * REACTIVATION SEQUENCING 174 * 175 * Structures can remain in memory, unaccessed, for long periods of time. 176 * This can cause the structure to wind up in an EXIS_TERMINATE state. 177 * The result is that stronger locks will be needed when looking up the 178 * structure and the code doing this can then re-activate the EXIS state 179 * by issuing exis_init(), and then re-cache (if desired) it via 180 * exis_cache(). 181 * 182 * Repeated lookups of the same structure are likely to remain cached 183 * for the caching period (N ticks, via the API) before having to refresh 184 * the structure again. Or indefinitely if the exis lock is in the 185 * LIVE state. 186 * 187 * Thus an EXIS_TERMIANTE state does *NOT* necessarily mean that the 188 * caller actually intends to terminate the structure, only that stronger 189 * locking will be required to return it to its fast-access state. 190 */ 191 192 #ifndef _SYS_EXISLOCK_H_ 193 #define _SYS_EXISLOCK_H_ 194 195 struct exislock { 196 long pseudo_ticks; 197 }; 198 typedef struct exislock exislock_t; 199 200 typedef enum exis_state { 201 EXIS_TERMINATE, 202 EXIS_NOTCACHED, 203 EXIS_CACHED, 204 EXIS_LIVE 205 } exis_state_t; 206 207 extern long pseudo_ticks; 208 209 #endif /* !_SYS_EXISLOCK_H_ */ 210