1 /* 2 * Copyright (c) 2020 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_HAZARD_H_ 30 #define _KERN_HAZARD_H_ 31 32 #include <sys/cdefs.h> 33 #include <kern/assert.h> 34 #include <mach/vm_types.h> 35 #include <os/atomic_private.h> 36 37 __BEGIN_DECLS 38 39 #ifdef XNU_KERNEL_PRIVATE 40 #pragma GCC visibility push(hidden) 41 42 /*! 43 * @file <kern/hazard.h> 44 * 45 * @brief 46 * Implementation of hazard pointers. 47 * 48 * @discussion 49 * Hazard pointers are fields that can be accessed when protected by special 50 * guards rather than traditional locks. 51 * 52 * <h2>Concepts</h2> 53 * 54 * Pointers used in this way must be declared with the @c HAZARD_POINTER macro. 55 * 56 * Guards can be "allocated" and "freed" using @c hazard_guard_get() and 57 * @c hazard_guard_set(). 58 * 59 * Then guards can be used to "acquire" the value of a hazardous pointer. 60 * 61 * 62 * <h2>Performance</h2> 63 * 64 * Acquiring through a guard has a relatively strong memory barrier, 65 * and its performance is at least as expensive as acquiring 66 * an uncontended lock. 67 * 68 * Releasing a guard (@c hazard_guard_put()) has a performance equivalent 69 * to releasing an uncontended lock. 70 * 71 * Acquiring through a reused guard combines both costs back to back. 72 * 73 * 74 * <h2>Recommended usage</h2> 75 * 76 * Hazard guards/pointers have a performance profile roughly similar 77 * to an uncontended lock when accessing a single pointer. 78 * 79 * It means that this technology isn't really suitable to protect a linked 80 * list (where the cost would have to be paid per element during a traversal), 81 * but works really well to protect access to a single pointer. 82 * 83 * This technology also has very strong guarantees in memory overhead, 84 * where the number of deferred deallocations is bounded by the number 85 * of guard slots. 86 * 87 * 88 * This is why the current implementation decides to only provide statically 89 * allocated CPU-local slots, which means that @c hazard_guard_get() will 90 * disable preemption and @c hazard_guard_put() re-enable it. 91 * 92 * Because the slots are statically allocated, oblivious nested use 93 * of hazard guards is not supported (Note: this could change provided 94 * a maximum "depth" of use can be guaranteed). 95 */ 96 97 98 #pragma mark - pointers allowing hazardous access 99 100 /*! 101 * @macro HAZARD_POINTER_DECL 102 * 103 * @brief 104 * Macro to declare a pointer type that uses hazard guards for access. 105 */ 106 #define HAZARD_POINTER_DECL(name, type_t) \ 107 struct name { type_t volatile __hazard_ptr; } 108 109 /*! 110 * @macro HAZARD_POINTER 111 * 112 * @brief 113 * Macro to declare a pointer that uses hazard guards for access. 114 */ 115 #define HAZARD_POINTER(type_t) \ 116 HAZARD_POINTER_DECL(, type_t) 117 118 /*! 119 * @macro hazard_ptr_init() 120 * 121 * @brief 122 * Initializes a @c HAZARD_POINTER() field to a specified value. 123 * 124 * @discussion 125 * The memory of @c value must have been initialized prior to this call. 126 * 127 * This is meant to be used in object initializers only, for updates to the 128 * pointer past initialization, use @c hazard_ptr_serialized_store(). 129 * 130 * @param ptr The hazard-protected pointer to initialize. 131 * @param value The value to initialize the poiner with. 132 */ 133 #define hazard_ptr_init(ptr, value) \ 134 __hazard_ptr_atomic_store(ptr, value, release) 135 136 /*! 137 * @macro hazard_ptr_clear() 138 * 139 * @brief 140 * Clears a @c HAZARD_POINTER() field. 141 * 142 * @param ptr The hazard-protected pointer to clear. 143 */ 144 #define hazard_ptr_clear(ptr) \ 145 __hazard_ptr_atomic_store(ptr, NULL, relaxed) 146 147 /*! 148 * @macro hazard_ptr_serialized_load_assert() 149 * 150 * @brief 151 * Read from a hazard protected pointer, while serialized by an external 152 * mechanism. 153 * 154 * @param ptr The hazard-protected pointer to read. 155 * @param held_cond An expression that can be asserted that the external 156 * mechanism is held. 157 */ 158 #define hazard_ptr_serialized_load_assert(ptr, held_cond) ({ \ 159 assertf(held_cond, "hazard_ptr_serialized_load: lock not held"); \ 160 (ptr)->__hazard_ptr; \ 161 }) 162 163 /*! 164 * @macro hazard_ptr_serialized_load() 165 * 166 * @brief 167 * Read from a hazard protected pointer, while serialized by an external 168 * mechanism. 169 * 170 * @param ptr The hazard-protected pointer to read. 171 */ 172 #define hazard_ptr_serialized_load(ptr) \ 173 hazard_ptr_serialized_load_assert(ptr, true) 174 175 /*! 176 * @macro hazard_ptr_load() 177 * 178 * @brief 179 * Read from a hazard protected pointer. 180 * 181 * @discussion 182 * Note that the returned value is not safe to dereference 183 * until it has been properly guarded. 184 * 185 * This is typically used in conjunction with @c hazard_guard_reuse_acquire(). 186 * 187 * @param ptr The hazard-protected pointer to read. 188 */ 189 #define hazard_ptr_load(ptr) \ 190 ({ (ptr)->__hazard_ptr; }) 191 192 /*! 193 * @macro hazard_ptr_serialized_store_assert() 194 * 195 * @brief 196 * Updates the value of a hazard protected pointer, while serialized by an 197 * external mechanism. 198 * 199 * @param ptr The hazard-protected pointer to read. 200 * @param value The value to update the poiner with. 201 * @param held_cond An expression that can be asserted that the external 202 * mechanism is held. 203 */ 204 #define hazard_ptr_serialized_store_assert(ptr, value, held_cond) ({ \ 205 assertf(held_cond, "hazard_ptr_serialized_store: lock not held"); \ 206 __hazard_ptr_atomic_store(ptr, value, release); \ 207 }) 208 209 /*! 210 * @macro hazard_ptr_serialized_store() 211 * 212 * @brief 213 * Updates the value of a hazard protected pointer, while serialized by an 214 * external mechanism. 215 * 216 * @param ptr The hazard-protected pointer to read. 217 * @param value The value to update the poiner with. 218 */ 219 #define hazard_ptr_serialized_store(ptr, value) \ 220 hazard_ptr_serialized_store_assert(ptr, value, true) 221 222 /*! 223 * @macro hazard_ptr_serialized_store_relaxed_assert() 224 * 225 * @brief 226 * Updates the value of a hazard protected pointer, while serialized by an 227 * external mechanism, without any barrier. 228 * 229 * @param ptr The hazard-protected pointer to read. 230 * @param value The value to update the poiner with. 231 * @param held_cond An expression that can be asserted that the external 232 * mechanism is held. 233 */ 234 #define hazard_ptr_serialized_store_relaxed_assert(ptr, value, held_cond) ({ \ 235 assertf(held_cond, "hazard_ptr_serialized_store: lock not held"); \ 236 __hazard_ptr_atomic_store(ptr, value, relaxed); \ 237 }) 238 239 /*! 240 * @macro hazard_ptr_serialized_store_relaxed() 241 * 242 * @brief 243 * Updates the value of a hazard protected pointer, while serialized by an 244 * external mechanism, without any barrier. 245 * 246 * @param ptr The hazard-protected pointer to read. 247 * @param value The value to update the poiner with. 248 */ 249 #define hazard_ptr_serialized_store_relaxed(ptr, value) \ 250 hazard_ptr_serialized_store_relaxed_assert(ptr, value, true) 251 252 /*! 253 * @macro hazard_retire() 254 * 255 * @brief 256 * Retires a pointer value that used to be assigned to a @c HAZARD_POINTER(). 257 * 258 * @param value The value to retire (must be pointer aligned). 259 * @param size An estimate of how much memory will be freed. 260 * @param destructor The destructor for the value. 261 */ 262 extern void 263 hazard_retire(void *value, vm_size_t size, void (*destructor)(void *)); 264 265 266 #pragma mark - hazard guards 267 268 /*! 269 * @typedef hazard_guard_t 270 * 271 * @brief 272 * The type for a hazard pointer guard. 273 */ 274 typedef struct hazard_guard { 275 os_atomic(void *) hg_val; 276 } *hazard_guard_t; 277 278 /*! 279 * @typedef hazard_guard_array_t 280 * 281 * @brief 282 * The type for a hazard pointer guard array. 283 */ 284 typedef struct hazard_guard *hazard_guard_array_t; 285 286 /*! 287 * @const HAZARD_GUARD_SLOTS 288 * 289 * @brief 290 * The number of static hazard guard slots available per CPU. 291 */ 292 #define HAZARD_GUARD_SLOTS 3 293 294 /*! 295 * @function hazard_guard_get() 296 * 297 * @brief 298 * Prepares a hazard guard slot to be used. 299 * 300 * @discussion 301 * This function disables preemption. 302 * 303 * When the guard slot is not longer needed, it must be disposed of 304 * using @c hazard_guard_put(). 305 * 306 * @param slot The static slot to start using. 307 */ 308 #define hazard_guard_get(slot) ({ \ 309 static_assert(slot < HAZARD_GUARD_SLOTS, "invalid slot #"); \ 310 __hazard_guard_get(slot, 1); \ 311 }) 312 313 /*! 314 * @function hazard_guard_get_n() 315 * 316 * @brief 317 * Prepares @c n contiguous hazard guard slots to be used. 318 * 319 * @discussion 320 * This function disables preemption. 321 * 322 * When the guard slot is not longer needed, it must be disposed of 323 * using @c hazard_guard_put_n(). 324 * 325 * @param slot The static slot to start using. 326 */ 327 #define hazard_guard_get_n(slot, n) ({ \ 328 static_assert(slot + n <= HAZARD_GUARD_SLOTS, "invalid slot #"); \ 329 __hazard_guard_get(slot, n); \ 330 }) 331 332 /*! 333 * @function hazard_guard_put() 334 * 335 * @brief 336 * Disposes of a hazard guard allocated with @c hazard_guard_get(). 337 * 338 * @param guard The hazard guard to dispose of. 339 */ 340 extern void 341 hazard_guard_put(hazard_guard_t guard); 342 343 /*! 344 * @function hazard_guard_put_n() 345 * 346 * @brief 347 * Disposes of @c n hazard guards allocated with @c hazard_guard_get_n(). 348 * 349 * @param array The hazard array to dispose of. 350 * @param n The number of guards allocated with 351 * @c hazard_guard_get_n() (must match). 352 */ 353 extern void 354 hazard_guard_put_n(hazard_guard_array_t array, size_t n); 355 356 /*! 357 * @function hazard_guard_dismiss() 358 * 359 * @brief 360 * Disposes of a hazard guard allocated with @c hazard_guard_get(). 361 * 362 * @discussion 363 * This variant doesn't have a memory barrier and should only be used 364 * when an external mechanism ensures that the guarded value stays pinned. 365 * 366 * @param guard The hazard guard to dispose of. 367 */ 368 extern void 369 hazard_guard_dismiss(hazard_guard_t guard); 370 371 /*! 372 * @function hazard_guard_dismiss_n() 373 * 374 * @brief 375 * Disposes of @c n hazard guard allocated with @c hazard_guard_get_n(). 376 * 377 * @discussion 378 * This variant doesn't have a memory barrier and should only be used 379 * when an external mechanism ensures that the guarded value stays pinned. 380 * 381 * @param guard The first hazard guard to dispose of. 382 * @param n The number of guards allocated with 383 * @c hazard_guard_get_n() (must match). 384 */ 385 extern void 386 hazard_guard_dismiss_n(hazard_guard_t guard, size_t n); 387 388 /*! 389 * @function hazard_guard_set() 390 * 391 * @brief 392 * Sets the value a guard will protect, 393 * in a guard that wasn't protecting anything. 394 * 395 * @discussion 396 * Most users will want to use the @c hazard_guard_acquire() 397 * wrapper instead. 398 * 399 * @param guard The hazard guard. 400 * @param value The value to protect. 401 */ 402 extern void 403 hazard_guard_set(hazard_guard_t guard, void *value); 404 405 /*! 406 * @function hazard_guard_replace() 407 * 408 * @brief 409 * Sets the value a guard will protect, 410 * in a guard that was previously protecting a value. 411 * 412 * @discussion 413 * Most users will want to use the @c hazard_guard_reuse_acquire() 414 * wrapper instead. 415 * 416 * @param guard The hazard guard. 417 * @param value The value to protect. 418 */ 419 extern void 420 hazard_guard_replace(hazard_guard_t guard, void *value); 421 422 /*! 423 * @function hazard_guard_acquire_val() 424 * 425 * @brief 426 * Acquire a guarded copy of a hazard pointer, 427 * using a guard that wasn't protecting anything. 428 * 429 * @param guard The hazard guard. 430 * @param ptr The pointer to read. 431 * @param val The current value of @c ptr 432 * (read with @c hazard_ptr_load()). 433 */ 434 #define hazard_guard_acquire_val(guard, ptr, val) ({ \ 435 __auto_type __p2 = (ptr); \ 436 __auto_type __val = (val); \ 437 hazard_guard_set(guard, __val); \ 438 __hazard_guard_acquire_loop(guard, __p2, __val); \ 439 }) 440 441 /*! 442 * @function hazard_guard_acquire() 443 * 444 * @brief 445 * Acquire a guarded copy of a hazard pointer, 446 * using a guard that wasn't protecting anything. 447 * 448 * @param guard The hazard guard. 449 * @param ptr The pointer to read. 450 */ 451 #define hazard_guard_acquire(guard, ptr) ({ \ 452 __auto_type __p1 = (ptr); \ 453 hazard_guard_acquire_val(guard, __p1, hazard_ptr_load(__p1)); \ 454 }) 455 456 /*! 457 * @function hazard_guard_reacquire_val() 458 * 459 * @brief 460 * Acquire a guarded copy of a hazard pointer, 461 * using a guard that was previously protecting a value. 462 * 463 * @param guard The hazard guard. 464 * @param ptr The pointer to read. 465 * @param val The current value of @c ptr. 466 */ 467 #define hazard_guard_reacquire_val(guard, ptr, val) ({ \ 468 __auto_type __p2 = (ptr); \ 469 __auto_type __val = (val); \ 470 hazard_guard_replace(guard, __val); \ 471 __hazard_guard_acquire_loop(guard, __p2, __val); \ 472 }) 473 474 /*! 475 * @function hazard_guard_reacquire() 476 * 477 * @brief 478 * Acquire a guarded copy of a hazard pointer, 479 * using a guard that was previously protecting a value. 480 * 481 * @param guard The hazard guard. 482 * @param ptr The pointer to read. 483 */ 484 #define hazard_guard_reacquire(guard, ptr) ({ \ 485 __auto_type __p1 = (ptr); \ 486 hazard_guard_reacquire_val(guard, __p1, hazard_ptr_load(__p1); \ 487 }) 488 489 490 #pragma mark - implementation details 491 492 extern hazard_guard_array_t 493 __hazard_guard_get(size_t slot, size_t count); 494 495 #define __hazard_guard_acquire_loop(guard, ptr, val) ({ \ 496 __auto_type __v1 = val; \ 497 for (;;) { \ 498 __auto_type __v2 = hazard_ptr_load(ptr); \ 499 if (__probable(__v1 == __v2)) { \ 500 break; \ 501 } \ 502 hazard_guard_set(guard, __v1 = __v2); \ 503 } \ 504 __v1; \ 505 }) 506 507 #define __hazard_ptr_atomic_store(ptr, value, order) ({ \ 508 os_atomic_thread_fence(order); \ 509 (ptr)->__hazard_ptr = (value); \ 510 }) 511 512 #if MACH_KERNEL_PRIVATE 513 extern void 514 hazard_register_mpsc_queue(void); 515 #endif 516 517 #pragma GCC visibility pop 518 #endif // XNU_KERNEL_PRIVATE 519 520 __END_DECLS 521 522 #endif /* _KERN_HAZARD_H_ */ 523