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#include <machine/asm.h> 30 31/* This section has all the code necessary for the atomic operations supported by 32 * OSAtomicFifoEnqueue, OSAtomicFifoDequeue APIs in libplatform. 33 * 34 * This code needs to be compiled as 1 section and should not make branches 35 * outside of this section. This allows us to copy the entire section to the 36 * text comm page once it is created - see osfmk/arm/commpage/commpage.c 37 * 38 * This section is split into 2 parts - the preemption-free zone (PFZ) routines 39 * and the preemptible routines (non-PFZ). The PFZ routines will not be 40 * preempted by the scheduler if the pc of the userspace process is in that 41 * region while handling asynchronous interrupts (note that traps are still 42 * possible in the PFZ). Instead, the scheduler will mark x15 (known through 43 * coordination with the functions in the commpage section) to indicate to the 44 * userspace code that it needs to take a delayed preemption. The PFZ functions 45 * may make callouts to preemptible routines and vice-versa. When a function 46 * returns to a preemptible routine after a callout to a function in the PFZ, it 47 * needs to check x15 to determine if a delayed preemption needs to be taken. In 48 * addition, functions in the PFZ should not have backwards branches. 49 * 50 * The entry point to execute code in the commpage text section is through the 51 * jump table at the very top of the section. The base of the jump table is 52 * exposed to userspace via the APPLE array and the offsets from the base of the 53 * jump table are listed in the arm/cpu_capabilities.h header. Adding any new 54 * functions in the PFZ requires a lockstep change to the cpu_capabilities.h 55 * header. 56 * 57 * Functions in PFZ: 58 * Enqueue function 59 * Dequeue function 60 * 61 * Functions not in PFZ: 62 * Backoff function as part of spin loop 63 * Preempt function to take delayed preemption as indicated by kernel 64 * 65 * ---------------------------------------------------------------------- 66 * 67 * The high level goal of the asm code in this section is to enqueue and dequeue 68 * from a FIFO linked list. 69 * 70 * typedef volatile struct { 71 * void *opaque1; <-- ptr to first queue element or null 72 * void *opaque2; <-- ptr to second queue element or null 73 * int opaque3; <-- spinlock 74 * } OSFifoQueueHead; 75 * 76 * This is done through a userspace spin lock stored in the linked list head 77 * for synchronization. 78 * 79 * Here is the pseudocode for the spin lock acquire algorithm which is split 80 * between the PFZ and the non-PFZ areas of the commpage text section. The 81 * pseudocode here is just for the enqueue operation but it is symmetrical for 82 * the dequeue operation. 83 * 84 * // Not in the PFZ. Entry from jump table. 85 * ENQUEUE() 86 * enqueued = TRY_LOCK_AND_ENQUEUE(lock_addr); 87 * // We're running here after running the TRY_LOCK_AND_ENQUEUE code in 88 * // the PFZ so we need to check if we need to take a delayed 89 * // preemption. 90 * if (kernel_wants_to_preempt_us){ 91 * // This is done through the pfz_exit() mach trap which is a dummy 92 * // syscall whose sole purpose is to allow the thread to enter the 93 * // kernel so that it can be preempted at AST. 94 * enter_kernel_to_take_delayed_preemption() 95 * } 96 * 97 * if (!enqueued) { 98 * ARM_MONITOR; 99 * WFE; 100 * enqueued = TRY_LOCK_AND_ENQUEUE(lock_addr); 101 * if (!enqueued) { 102 * // We failed twice, take a backoff 103 * BACKOFF(); 104 * goto ENQUEUE() 105 * } else { 106 * // We got here from PFZ, check for delayed preemption 107 * if (kernel_wants_to_preempt_us){ 108 * enter_kernel_to_take_delayed_preemption() 109 * } 110 * } 111 * } 112 * 113 * // in PFZ 114 * TRY_LOCK_AND_ENQUEUE(): 115 * is_locked = try_lock(lock_addr); 116 * if (is_locked) { 117 * <do enqueue operation> 118 * return true 119 * } else { 120 * return false 121 * } 122 * 123 * 124 * // Not in the PFZ 125 * BACKOFF(): 126 * // We're running here after running the TRY_LOCK_AND_ENQUEUE code in 127 * // the PFZ so we need to check if we need to take a delayed 128 * // preemption. 129 * if (kernel_wants_to_preempt_us) { 130 * enter_kernel_to_take_preemption() 131 * } else { 132 * // Note that it is safe to do this loop here since the entire 133 * // BACKOFF function isn't in the PFZ and so can be preempted at any 134 * // time 135 * do { 136 * lock_is_free = peek(lock_addr); 137 * if (lock_is_free) { 138 * return 139 * } else { 140 * pause_with_monitor(lock_addr) 141 * } 142 * } while (1) 143 * } 144 */ 145 146/* Macros and helpers */ 147 148.macro BACKOFF lock_addr 149 // Save registers we can't clobber 150 stp x0, x1, [sp, #-16]! 151 stp x2, x9, [sp, #-16]! 152 153 // Pass in lock addr to backoff function 154 mov x0, \lock_addr 155 bl _backoff // Jump out of the PFZ zone now 156 157 // Restore registers 158 ldp x2, x9, [sp], #16 159 ldp x0, x1, [sp], #16 160.endmacro 161 162/* x0 = pointer to queue head 163 * x1 = pointer to new elem to enqueue 164 * x2 = offset of link field inside element 165 * x3 = Address of lock 166 * 167 * Moves result of the helper function to the register specified 168 */ 169.macro TRYLOCK_ENQUEUE result 170 stp x0, xzr, [sp, #-16]! // Save x0 since it'll be clobbered by return value 171 172 bl _pfz_trylock_and_enqueue 173 mov \result, x0 174 175 ldp x0, xzr, [sp], #16 // Restore saved registers 176.endmacro 177 178/* x0 = pointer to queue head 179 * x1 = offset of link field inside element 180 * x2 = Address of lock 181 * 182 * Moves result of the helper function to the register specified 183 */ 184.macro TRYLOCK_DEQUEUE result 185 stp x0, xzr, [sp, #-16]! // Save x0 since it'll be clobbered by return value 186 187 bl _pfz_trylock_and_dequeue 188 mov \result, x0 189 190 ldp x0, xzr, [sp], #16 // Restore saved registers 191.endmacro 192 193/* 194 * Takes a delayed preemption if needed and then branches to the label 195 * specified. 196 * 197 * Modifies x15 198 */ 199.macro PREEMPT_SELF_THEN branch_to_take_on_success 200 cbz x15, \branch_to_take_on_success // No delayed preemption to take, just try again 201 202 mov x15, xzr // zero out the preemption pending field 203 bl _preempt_self 204 b \branch_to_take_on_success 205.endmacro 206 207 .section __TEXT_EXEC,__commpage_text,regular,pure_instructions 208 209 /* Preemption free functions */ 210 .align 2 211_jump_table: // 32 entry jump table, only 2 are used 212 b _pfz_enqueue 213 b _pfz_dequeue 214 brk #666 215 brk #666 216 brk #666 217 brk #666 218 brk #666 219 brk #666 220 brk #666 221 brk #666 222 brk #666 223 brk #666 224 brk #666 225 brk #666 226 brk #666 227 brk #666 228 brk #666 229 brk #666 230 brk #666 231 brk #666 232 brk #666 233 brk #666 234 brk #666 235 brk #666 236 brk #666 237 brk #666 238 brk #666 239 brk #666 240 brk #666 241 brk #666 242 brk #666 243 brk #666 244 245 246/* 247 * typedef volatile struct { 248 * void *opaque1; <-- ptr to first queue element or null 249 * void *opaque2; <-- ptr to second queue element or null 250 * int opaque3; <-- spinlock 251 * } osfifoqueuehead; 252 */ 253 254/* Non-preemptible helper routine to FIFO enqueue: 255 * int pfz_trylock_and_enqueue(OSFifoQueueHead *__list, void *__new, size_t __offset, uint32_t *lock_addr); 256 * 257 * x0 = pointer to queue head structure 258 * x1 = pointer to new element to enqueue 259 * x2 = offset of link field inside element 260 * x3 = address of lock 261 * 262 * Only caller save registers (x9 - x15) are used in this function 263 * 264 * Returns 0 on success and non-zero value on failure 265 */ 266 .globl _pfz_trylock_and_enqueue 267 .align 2 268_pfz_trylock_and_enqueue: 269 ARM64_STACK_PROLOG 270 PUSH_FRAME 271 272 mov w10, wzr // unlock value = w10 = 0 273 mov w11, #1 // locked value = w11 = 1 274 275 // Try to grab the lock 276 casa w10, w11, [x3] // Atomic CAS with acquire barrier 277 cbz w10, Ltrylock_enqueue_success 278 279 mov x0, #-1 // Failed 280 b Ltrylock_enqueue_exit 281 282 /* We got the lock, enqueue the element */ 283 284Ltrylock_enqueue_success: 285 ldr x10, [x0, #8] // x10 = tail of the queue 286 cbnz x10, Lnon_empty_queue // tail not NULL 287 str x1, [x0] // Set head to new element 288 b Lset_new_tail 289 290Lnon_empty_queue: 291 str x1, [x10, x2] // Set old tail -> offset = new elem 292 293Lset_new_tail: 294 str x1, [x0, #8] // Set tail = new elem 295 296 // Drop spin lock with release barrier (pairs with acquire in casa) 297 stlr wzr, [x3] 298 299 mov x0, xzr // Mark success 300 301Ltrylock_enqueue_exit: 302 POP_FRAME 303 ARM64_STACK_EPILOG 304 305/* Non-preemptible helper routine to FIFO dequeue: 306 * void *pfz_trylock_and_dequeue(OSFifoQueueHead *__list, size_t __offset, uint32_t *lock_addr); 307 * 308 * x0 = pointer to queue head structure 309 * x1 = pointer to new element to enqueue 310 * x2 = address of lock 311 * 312 * Only caller save registers (x9 - x15) are used in this function 313 * 314 * Returns -1 on failure, and the pointer on success (can be NULL) 315 */ 316 .globl _pfz_trylock_and_dequeue 317 .align 2 318_pfz_trylock_and_dequeue: 319 ARM64_STACK_PROLOG 320 PUSH_FRAME 321 322 // Try to grab the lock 323 mov w10, wzr // unlock value = w10 = 0 324 mov w11, #1 // locked value = w11 = 1 325 326 casa w10, w11, [x2] // Atomic CAS with acquire barrier 327 cbz w10, Ltrylock_dequeue_success 328 329 mov x0, #-1 // Failed 330 b Ltrylock_dequeue_exit 331 332 /* We got the lock, dequeue the element */ 333Ltrylock_dequeue_success: 334 ldr x10, [x0] // x10 = head of the queue 335 cbz x10, Lreturn_head // if head is null, return 336 337 ldr x11, [x10, x1] // get ptr to new head 338 cbnz x11, Lupdate_new_head // If new head != NULL, then not singleton. Only need to update head 339 340 // Singleton case 341 str xzr, [x0, #8] // dequeuing from singleton queue, update tail to NULL 342 343Lupdate_new_head: 344 str xzr, [x10, x1] // zero the link in the old head 345 str x11, [x0] // Set up a new head 346 347Lreturn_head: 348 mov x0, x10 // Move head to x0 349 stlr wzr, [x2] // Drop spin lock with release barrier (pairs with acquire in casa) 350 351Ltrylock_dequeue_exit: 352 POP_FRAME 353 ARM64_STACK_EPILOG 354 355 356 /* Preemptible functions */ 357 .private_extern _commpage_text_preemptible_functions 358_commpage_text_preemptible_functions: 359 360 361/* 362 * void pfz_enqueue(OSFifoQueueHead *__list, void *__new, size_t __offset); 363 * x0 = pointer to queue head 364 * x1 = pointer to new elem to enqueue 365 * x2 = offset of link field inside element 366 */ 367 .globl _pfz_enqueue 368 369 .align 2 370_pfz_enqueue: 371 ARM64_STACK_PROLOG 372 PUSH_FRAME 373 374 str xzr, [x1, x2] // Zero the forward link in the new element 375 mov x15, xzr // zero out the register used to communicate with kernel 376 377 add x3, x0, #16 // address of lock = x3 = x0 + 16 378Lenqueue_trylock_loop: 379 380 // Attempt #1 381 TRYLOCK_ENQUEUE x9 382 PREEMPT_SELF_THEN Lenqueue_determine_success 383 384Lenqueue_determine_success: 385 386 cbz x9, Lenqueue_success // did we succeed? if so, exit 387 388 ldxr w9, [x3] // arm the monitor for the lock address 389 cbz w9, Lenqueue_clear_monitor // lock is available, retry. 390 391 wfe // Wait with monitor armed 392 393 // Attempt #2 394 TRYLOCK_ENQUEUE x9 395 cbz x9, Lenqueue_take_delayed_preemption_upon_success // did we succeed? if so, exit 396 397 // We failed twice - backoff then try again 398 399 BACKOFF x3 400 b Lenqueue_trylock_loop 401 402Lenqueue_clear_monitor: 403 clrex // Pairs with the ldxr 404 405 // Take a preemption if needed then branch to enqueue_trylock_loop 406 PREEMPT_SELF_THEN Lenqueue_trylock_loop 407 408Lenqueue_take_delayed_preemption_upon_success: 409 PREEMPT_SELF_THEN Lenqueue_success 410 411Lenqueue_success: 412 POP_FRAME 413 ARM64_STACK_EPILOG 414 415/* 416 * void *pfz_dequeue(OSFifoQueueHead *__list, size_t __offset); 417 * x0 = pointer to queue head 418 * x1 = offset of link field inside element 419 * 420 * This function is not in the PFZ but calls out to a helper which is in the PFZ 421 * (_pfz_trylock_and_dequeue) 422 */ 423 .globl _pfz_dequeue 424 .align 2 425_pfz_dequeue: 426 ARM64_STACK_PROLOG 427 PUSH_FRAME 428 429 mov x15, xzr // zero out the register used to communicate with kernel 430 431 add x2, x0, #16 // address of lock = x2 = x0 + 16 432Ldequeue_trylock_loop: 433 434 // Attempt #1 435 TRYLOCK_DEQUEUE x9 436 PREEMPT_SELF_THEN Ldequeue_determine_success 437 438Ldequeue_determine_success: 439 cmp x9, #-1 // is result of dequeue == -1? 440 b.ne Ldequeue_success // no, we succeeded 441 442 ldxr w9, [x2] // arm the monitor for the lock address 443 cbz w9, Ldequeue_clear_monitor // lock is available, retry. 444 445 wfe // Wait with monitor armed 446 447 // Attempt #2 448 TRYLOCK_DEQUEUE x9 449 cmp x9, #-1 // did we fail? 450 b.ne Ldequeue_take_delayed_preemption_upon_success // no, we succeeded 451 452 // We failed twice - backoff then try again 453 454 BACKOFF x2 455 b Ldequeue_trylock_loop 456 457Ldequeue_take_delayed_preemption_upon_success: 458 // We just got here after executing PFZ code, check if we need a preemption 459 PREEMPT_SELF_THEN Ldequeue_success 460 461Ldequeue_clear_monitor: 462 clrex // Pairs with the ldxr 463 // Take a preemption if needed then branch to dequeue_trylock_loop. 464 PREEMPT_SELF_THEN Ldequeue_trylock_loop 465 466Ldequeue_success: 467 mov x0, x9 // Move x9 (where result was stored earlier) to x0 468 POP_FRAME 469 ARM64_STACK_EPILOG 470 471 472/* void preempt_self(void) 473 * 474 * Make a syscall to take a preemption. This function is not in the PFZ. 475 */ 476 .align 2 477_preempt_self: 478 ARM64_STACK_PROLOG 479 PUSH_FRAME 480 481 // Save registers on which will be clobbered by mach trap on stack and keep 482 // it 16 byte aligned 483 stp x0, x1, [sp, #-16]! 484 485 // Note: We don't need to caller save registers since svc will trigger an 486 // exception and kernel will save and restore register state 487 488 // Make syscall to take delayed preemption 489 mov x16, #-58 // -58 = pfz_exit 490 svc #0x80 491 492 // Restore registers from stack 493 ldp x0, x1, [sp], #16 494 495 POP_FRAME 496 ARM64_STACK_EPILOG 497 498/* 499 * void backoff(uint32_t *lock_addr); 500 * The function returns when it observes that the lock has become available. 501 * This function is not in the PFZ. 502 * 503 * x0 = lock address 504 */ 505 .align 2 506 .globl _backoff 507_backoff: 508 ARM64_STACK_PROLOG 509 PUSH_FRAME 510 511 cbz x15, Lno_preempt // Kernel doesn't want to preempt us, jump to loop 512 513 mov x15, xzr // zero out the preemption pending field 514 bl _preempt_self 515 516Lno_preempt: 517 ldxr w9, [x0] // Snoop on lock and arm the monitor 518 cbz w9, Lend_backoff // The lock seems to be available, return 519 520 wfe // pause 521 522 b Lno_preempt 523 524Lend_backoff: 525 clrex 526 527 POP_FRAME 528 ARM64_STACK_EPILOG 529