1 /* 2 * Copyright (c) 2021 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29 #ifndef _KERN_TICKET_LOCK_H_ 30 #define _KERN_TICKET_LOCK_H_ 31 32 #ifndef __ASSEMBLER__ 33 #include <kern/assert.h> 34 #include <kern/lock_types.h> 35 #include <kern/lock_group.h> 36 #if XNU_KERNEL_PRIVATE 37 #include <kern/counter.h> 38 #endif /* XNU_KERNEL_PRIVATE */ 39 #endif /* __ASSEMBLER__ */ 40 41 #ifndef __ASSEMBLER__ 42 43 __BEGIN_DECLS 44 #pragma GCC visibility push(hidden) 45 46 #ifdef MACH_KERNEL_PRIVATE 47 48 /*! 49 * @typedef hw_lck_ticket_t 50 * 51 * @discussion 52 * This type describes the low level type for a ticket lock. 53 * @c lck_ticket_t provides a higher level abstraction 54 * that also provides thread ownership information. 55 * 56 * This is a low level lock meant to be part of data structures 57 * that are very constrained on space, or is part of a larger lock. 58 * 59 * This lower level interface supports an @c *_allow_invalid() 60 * to implement advanced memory reclamation schemes using sequestering. 61 * Do note that when @c CONFIG_PROB_GZALLOC is engaged, and the target lock 62 * comes from a zone, PGZ must be handled manually. 63 * See ipc_object_lock_allow_invalid() for an example of that. 64 * 65 * @c hw_lck_ticket_invalidate() must be used on locks 66 * that will be used this way: in addition to make subsequent calls to 67 * @c hw_lck_ticket_lock_allow_invalid() to fail, it allows for 68 * @c hw_lck_ticket_destroy() to synchronize with callers to 69 * @c hw_lck_ticket_lock_allow_invalid() who successfully reserved 70 * a ticket but will fail, ensuring the memory can't be freed too early. 71 * 72 * 73 * @c hw_lck_ticket_reserve() can be used to pre-reserve a ticket. 74 * When this function returns @c true, then the lock was acquired. 75 * When it returns @c false, then @c hw_lck_ticket_wait() must 76 * be called to wait for this ticket. 77 * 78 * This can be used to resolve certain lock inversions: assuming 79 * two locks, @c L (a mutex or any kind of lock) and @c T (a ticket lock), 80 * where @c L can be taken when @c T is held but not the other way around, 81 * then the following can be done to take both locks in "the wrong order", 82 * with a guarantee of forward progress: 83 * 84 * <code> 85 * // starts with L held 86 * uint32_t ticket; 87 * 88 * if (!hw_lck_ticket_reserve(T, &ticket)) { 89 * unlock(L); 90 * hw_lck_ticket_wait(T, ticket): 91 * lock(L); 92 * // possibly validate what might have changed 93 * // due to dropping L 94 * } 95 * 96 * // both L and T are held 97 * </code> 98 * 99 * This pattern above is safe even for a case when the protected 100 * resource contains the ticket lock @c T, provided that it is 101 * guaranteed that both @c T and @c L (in the proper order) will 102 * be taken before that resource death. In that case, in the resource 103 * destructor, when @c hw_lck_ticket_destroy() is called, it will 104 * wait for the reservation to be released. 105 * 106 * See @c waitq_pull_thread_locked() for an example of this where: 107 * - @c L is the thread lock of a thread waiting on a given waitq, 108 * - @c T is the lock for that waitq, 109 * - the waitq can't be destroyed before the thread is unhooked from it, 110 * which happens under both @c L and @c T. 111 * 112 * 113 * @note: 114 * At the moment, this construct only supports up to 255 CPUs. 115 * Supporting more CPUs requires losing the `lck_type` field, 116 * and burning the low bit of the cticket/nticket 117 * for the "invalidation" feature. 118 */ 119 typedef union hw_lck_ticket_s { 120 struct { 121 uint8_t lck_type; 122 uint8_t lck_valid : 1; 123 uint8_t lck_is_pv : 1; 124 uint8_t lck_unused : 6; 125 union { 126 struct { 127 uint8_t cticket; 128 uint8_t nticket; 129 }; 130 uint16_t tcurnext; 131 }; 132 }; 133 uint32_t lck_value; 134 } hw_lck_ticket_t; 135 136 /*! 137 * @typedef lck_ticket_t 138 * 139 * @discussion 140 * A higher level construct than hw_lck_ticket_t in 2 words 141 * like other kernel locks, which admits thread ownership information. 142 */ 143 typedef struct lck_ticket_s { 144 uint32_t __lck_ticket_unused : 24; 145 uint32_t lck_ticket_type : 8; 146 uint32_t lck_ticket_padding; 147 hw_lck_ticket_t tu; 148 uint32_t lck_ticket_owner; 149 } lck_ticket_t; 150 151 #else /* !MACH_KERNEL_PRIVATE */ 152 153 typedef struct { 154 uint32_t opaque0; 155 uint32_t opaque1; 156 uint32_t opaque2; 157 uint32_t opaque3; 158 } lck_ticket_t; 159 160 #endif /* !MACH_KERNEL_PRIVATE */ 161 #if MACH_KERNEL_PRIVATE 162 163 #if !LCK_GRP_USE_ARG 164 #define hw_lck_ticket_init(lck, grp) hw_lck_ticket_init(lck) 165 #define hw_lck_ticket_init_locked(lck, grp) hw_lck_ticket_init_locked(lck) 166 #define hw_lck_ticket_destroy(lck, grp) hw_lck_ticket_destroy(lck) 167 #define hw_lck_ticket_lock(lck, grp) hw_lck_ticket_lock(lck) 168 #define hw_lck_ticket_lock_nopreempt(lck, grp) hw_lck_ticket_lock_nopreempt(lck) 169 #define hw_lck_ticket_lock_to(lck, pol, grp) hw_lck_ticket_lock_to(lck, pol) 170 #define hw_lck_ticket_lock_nopreempt_to(lck, pol, grp) \ 171 hw_lck_ticket_lock_nopreempt_to(lck, pol) 172 #define hw_lck_ticket_lock_try(lck, grp) hw_lck_ticket_lock_try(lck) 173 #define hw_lck_ticket_lock_try_nopreempt(lck, grp) \ 174 hw_lck_ticket_lock_try_nopreempt(lck) 175 #define hw_lck_ticket_lock_allow_invalid(lck, pol, grp) \ 176 hw_lck_ticket_lock_allow_invalid(lck, pol) 177 #define hw_lck_ticket_reserve(lck, t, grp) hw_lck_ticket_reserve(lck, t) 178 #define hw_lck_ticket_reserve_nopreempt(lck, t, grp) \ 179 hw_lck_ticket_reserve_nopreempt(lck, t) 180 #define hw_lck_ticket_reserve_allow_invalid(lck, t, grp) \ 181 hw_lck_ticket_reserve_allow_invalid(lck, t) 182 #define hw_lck_ticket_wait(lck, ticket, pol, grp) \ 183 hw_lck_ticket_wait(lck, ticket, pol) 184 #endif /* !LCK_GRP_USE_ARG */ 185 186 187 /* init/destroy */ 188 189 extern void hw_lck_ticket_init( 190 hw_lck_ticket_t *tlock, 191 lck_grp_t *grp); 192 193 extern void hw_lck_ticket_init_locked( 194 hw_lck_ticket_t *tlock, 195 lck_grp_t *grp); 196 197 extern void hw_lck_ticket_destroy( 198 hw_lck_ticket_t *tlock, 199 lck_grp_t *grp); 200 201 extern void hw_lck_ticket_invalidate( 202 hw_lck_ticket_t *tlock); 203 204 extern bool hw_lck_ticket_held( 205 hw_lck_ticket_t *tlock) __result_use_check; 206 207 208 /* lock */ 209 210 extern void hw_lck_ticket_lock( 211 hw_lck_ticket_t *tlock, 212 lck_grp_t *grp); 213 214 extern void hw_lck_ticket_lock_nopreempt( 215 hw_lck_ticket_t *tlock, 216 lck_grp_t *grp); 217 218 extern hw_lock_status_t hw_lck_ticket_lock_to( 219 hw_lck_ticket_t *tlock, 220 hw_spin_policy_t policy, 221 lck_grp_t *grp); 222 223 extern hw_lock_status_t hw_lck_ticket_lock_nopreempt_to( 224 hw_lck_ticket_t *tlock, 225 hw_spin_policy_t policy, 226 lck_grp_t *grp); 227 228 229 /* lock_try */ 230 231 extern bool hw_lck_ticket_lock_try( 232 hw_lck_ticket_t *tlock, 233 lck_grp_t *grp) __result_use_check; 234 235 extern bool hw_lck_ticket_lock_try_nopreempt( 236 hw_lck_ticket_t *tlock, 237 lck_grp_t *grp) __result_use_check; 238 239 240 /* unlock */ 241 242 extern void hw_lck_ticket_unlock( 243 hw_lck_ticket_t *tlock); 244 245 extern void hw_lck_ticket_unlock_nopreempt( 246 hw_lck_ticket_t *tlock); 247 248 249 /* reserve/wait */ 250 251 extern bool hw_lck_ticket_reserve( 252 hw_lck_ticket_t *tlock, 253 uint32_t *ticket, 254 lck_grp_t *grp) __result_use_check; 255 256 extern bool hw_lck_ticket_reserve_nopreempt( 257 hw_lck_ticket_t *tlock, 258 uint32_t *ticket, 259 lck_grp_t *grp) __result_use_check; 260 261 extern hw_lock_status_t hw_lck_ticket_reserve_allow_invalid( 262 hw_lck_ticket_t *tlock, 263 uint32_t *ticket, 264 lck_grp_t *grp) __result_use_check; 265 266 extern hw_lock_status_t hw_lck_ticket_wait( 267 hw_lck_ticket_t *tlock, 268 uint32_t ticket, 269 hw_spin_policy_t policy, 270 lck_grp_t *grp); 271 272 extern hw_lock_status_t hw_lck_ticket_lock_allow_invalid( 273 hw_lck_ticket_t *tlock, 274 hw_spin_policy_t policy, 275 lck_grp_t *grp); 276 277 /* pv */ 278 279 extern void hw_lck_ticket_unlock_kick_pv( 280 hw_lck_ticket_t *tlock, 281 uint8_t value); 282 283 extern void hw_lck_ticket_lock_wait_pv( 284 hw_lck_ticket_t *tlock, 285 uint8_t value); 286 287 #endif /* MACH_KERNEL_PRIVATE */ 288 #if XNU_KERNEL_PRIVATE 289 290 extern bool kdp_lck_ticket_is_acquired( 291 lck_ticket_t *tlock) __result_use_check; 292 293 extern void lck_ticket_lock_nopreempt( 294 lck_ticket_t *tlock, 295 lck_grp_t *grp); 296 297 extern bool lck_ticket_lock_try( 298 lck_ticket_t *tlock, 299 lck_grp_t *grp) __result_use_check; 300 301 extern bool lck_ticket_lock_try_nopreempt( 302 lck_ticket_t *tlock, 303 lck_grp_t *grp) __result_use_check; 304 305 extern void lck_ticket_unlock_nopreempt( 306 lck_ticket_t *tlock); 307 308 #endif /* XNU_KERNEL_PRIVATE */ 309 310 extern __exported void lck_ticket_init( 311 lck_ticket_t *tlock, 312 lck_grp_t *grp); 313 314 extern __exported void lck_ticket_destroy( 315 lck_ticket_t *tlock, 316 lck_grp_t *grp); 317 318 extern __exported void lck_ticket_lock( 319 lck_ticket_t *tlock, 320 lck_grp_t *grp); 321 322 extern __exported void lck_ticket_unlock( 323 lck_ticket_t *tlock); 324 325 extern __exported void lck_ticket_assert_owned( 326 const lck_ticket_t *tlock); 327 328 extern __exported void lck_ticket_assert_not_owned( 329 const lck_ticket_t *tlock); 330 331 #define LCK_TICKET_ASSERT_OWNED(tlock) \ 332 MACH_ASSERT_DO(lck_ticket_assert_owned(tlock)) 333 #define LCK_TICKET_ASSERT_NOT_OWNED(tlock) \ 334 MACH_ASSERT_DO(lck_ticket_assert_not_owned(tlock)) 335 336 #pragma GCC visibility pop 337 __END_DECLS 338 339 #endif /* __ASSEMBLER__ */ 340 #if XNU_KERNEL_PRIVATE 341 342 #define HW_LCK_TICKET_LOCK_VALID_BIT 8 343 344 #if CONFIG_PV_TICKET 345 346 /* 347 * For the PV case, the lsbit of cticket is treated as as wait flag, 348 * and the ticket counters are incremented by 2 349 */ 350 #define HW_LCK_TICKET_LOCK_PVWAITFLAG ((uint8_t)1) 351 #define HW_LCK_TICKET_LOCK_INCREMENT ((uint8_t)2) 352 #define HW_LCK_TICKET_LOCK_INC_WORD 0x02000000 353 354 #if !defined(__ASSEMBLER__) && (DEBUG || DEVELOPMENT) 355 /* counters for sysctls */ 356 SCALABLE_COUNTER_DECLARE(ticket_wflag_cleared); 357 SCALABLE_COUNTER_DECLARE(ticket_wflag_still); 358 SCALABLE_COUNTER_DECLARE(ticket_just_unlock); 359 SCALABLE_COUNTER_DECLARE(ticket_kick_count); 360 SCALABLE_COUNTER_DECLARE(ticket_wait_count); 361 SCALABLE_COUNTER_DECLARE(ticket_already_count); 362 SCALABLE_COUNTER_DECLARE(ticket_spin_count); 363 #define PVTICKET_STATS_ADD(var, i) counter_add_preemption_disabled(&ticket_##var, (i)) 364 #define PVTICKET_STATS_INC(var) counter_inc_preemption_disabled(&ticket_##var) 365 #else 366 #define PVTICKET_STATS_ADD(var, i) /* empty */ 367 #define PVTICKET_STATS_INC(var) /* empty */ 368 #endif 369 370 #else /* CONFIG_PV_TICKET */ 371 372 #define HW_LCK_TICKET_LOCK_PVWAITFLAG ((uint8_t)0) 373 #define HW_LCK_TICKET_LOCK_INCREMENT ((uint8_t)1) 374 #define HW_LCK_TICKET_LOCK_INC_WORD 0x01000000 375 376 #endif /* CONFIG_PV_TICKET */ 377 #endif /* XNU_KERNEL_PRIVATE */ 378 #endif /* _KERN_TICKET_LOCK_H_ */ 379