2 * Copyright (c) 2020 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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
35 * Existential Lock implementation
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.
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!).
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.
58 * API (see sys/exislock2.h)
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.
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
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.
77 * Unconditionally initialize the exis structure, placing it in a
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).
87 * Values should not generally be interpreted beyond this. Instead,
88 * use exis_state(), exis_usable(), and exis_freeable().
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.
99 * Returns non-zero if the exis structure is usable, meaning that it
100 * is in a LIVE or CACHED state (>= 0).
104 * Returns non-zero if the exis structure is usable, meaning that it
105 * is in a TERMINATE state (<= -2).
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.
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
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).
128 * A structure in any other state will not be modified and FALSE will
131 * The value (0) can be passed to cause the structure to enter into
132 * a CACHED state with the least timeout.
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.
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.
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.
150 * TERMINATION SEQUENCING
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.
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.
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.
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.
170 * --- Additional TERMINATE states may be sequenced if necessary, there
173 * REACTIVATION SEQUENCING
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
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
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.
192 #ifndef _SYS_EXISLOCK_H_
193 #define _SYS_EXISLOCK_H_
198 typedef struct exislock exislock_t;
200 typedef enum exis_state {
207 extern long pseudo_ticks;
209 #endif /* !_SYS_EXISLOCK_H_ */