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