bsd/kern/sys_ulock.c

   1 /*
   2  * Copyright (c) 2015 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/atomic.h>
  30
  31 #include <sys/param.h>
  32 #include <sys/systm.h>
  33 #include <sys/ioctl.h>
  34 #include <sys/file_internal.h>
  35 #include <sys/proc_internal.h>
  36 #include <sys/kernel.h>
  37 #include <sys/guarded.h>
  38 #include <sys/stat.h>
  39 #include <sys/malloc.h>
  40 #include <sys/sysproto.h>
  41 #include <sys/pthread_shims.h>
  42
  43 #include <mach/mach_types.h>
  44
  45 #include <kern/cpu_data.h>
  46 #include <kern/mach_param.h>
  47 #include <kern/kern_types.h>
  48 #include <kern/assert.h>
  49 #include <kern/kalloc.h>
  50 #include <kern/thread.h>
  51 #include <kern/clock.h>
  52 #include <kern/ledger.h>
  53 #include <kern/policy_internal.h>
  54 #include <kern/task.h>
  55 #include <kern/telemetry.h>
  56 #include <kern/waitq.h>
  57 #include <kern/sched_prim.h>
  58 #include <kern/turnstile.h>
  59 #include <kern/zalloc.h>
  60 #include <kern/debug.h>
  61
  62 #include <pexpert/pexpert.h>
  63
  64 #define XNU_TEST_BITMAP
  65 #include <kern/bits.h>
  66
  67 #include <os/hash.h>
  68 #include <sys/ulock.h>
  69
  70 /*
  71  * How ulock promotion works:
  72  *
  73  * There’s a requested policy field on every thread called ‘promotions’, which
  74  * expresses which ulock promotions are happening to this thread.
  75  * The promotion priority saturates until the promotion count goes to 0.
  76  *
  77  * We also track effective promotion qos, which is the qos before clamping.
  78  * This value is used for promoting a thread that another thread is waiting on,
  79  * so that the lock owner reinflates to the right priority after unclamping.
  80  *
  81  * This also works for non-QoS threads, which can donate base priority to QoS
  82  * and non-QoS threads alike.
  83  *
  84  * ulock wait applies a promotion to the owner communicated through
  85  * UL_UNFAIR_LOCK as waiters block, and that promotion is saturated as long as
  86  * there is still an owner.  In ulock wake, if the waker is still the owner,
  87  * then it clears its ownership and drops the boost.  It does NOT transfer
  88  * ownership/priority boost to the new thread.  Instead, it selects the
  89  * waiting thread with the highest base priority to be woken next, and
  90  * relies on that thread to carry the torch for the other waiting threads.
  91  */
  92
  93 static lck_grp_t *ull_lck_grp;
  94
  95 typedef lck_spin_t ull_lock_t;
  96 #define ull_lock_init(ull)      lck_spin_init(&ull->ull_lock, ull_lck_grp, NULL)
  97 #define ull_lock_destroy(ull)   lck_spin_destroy(&ull->ull_lock, ull_lck_grp)
  98 #define ull_lock(ull)           lck_spin_lock_grp(&ull->ull_lock, ull_lck_grp)
  99 #define ull_unlock(ull)         lck_spin_unlock(&ull->ull_lock)
 100 #define ull_assert_owned(ull)   LCK_SPIN_ASSERT(&ull->ull_lock, LCK_ASSERT_OWNED)
 101 #define ull_assert_notwned(ull) LCK_SPIN_ASSERT(&ull->ull_lock, LCK_ASSERT_NOTOWNED)
 102
 103 #define ULOCK_TO_EVENT(ull)   ((event_t)ull)
 104 #define EVENT_TO_ULOCK(event) ((ull_t *)event)
 105
 106 typedef enum {
 107         ULK_INVALID = 0,
 108         ULK_UADDR,
 109         ULK_XPROC,
 110 } ulk_type;
 111
 112 typedef struct {
 113         union {
 114                 struct __attribute__((packed)) {
 115                         user_addr_t     ulk_addr;
 116                         pid_t           ulk_pid;
 117                 };
 118                 struct __attribute__((packed)) {
 119                         uint64_t        ulk_object;
 120                         uint64_t        ulk_offset;
 121                 };
 122         };
 123         ulk_type        ulk_key_type;
 124 } ulk_t;
 125
 126 #define ULK_UADDR_LEN   (sizeof(user_addr_t) + sizeof(pid_t))
 127 #define ULK_XPROC_LEN   (sizeof(uint64_t) + sizeof(uint64_t))
 128
 129 inline static bool
 130 ull_key_match(ulk_t *a, ulk_t *b)
 131 {
 132         if (a->ulk_key_type != b->ulk_key_type) {
 133                 return false;
 134         }
 135
 136         if (a->ulk_key_type == ULK_UADDR) {
 137                 return (a->ulk_pid == b->ulk_pid) &&
 138                        (a->ulk_addr == b->ulk_addr);
 139         }
 140
 141         assert(a->ulk_key_type == ULK_XPROC);
 142         return (a->ulk_object == b->ulk_object) &&
 143                (a->ulk_offset == b->ulk_offset);
 144 }
 145
 146 typedef struct ull {
 147         /*
 148          * ull_owner is the most recent known value for the owner of this ulock
 149          * i.e. it may be out of date WRT the real value in userspace.
 150          */
 151         thread_t        ull_owner; /* holds +1 thread reference */
 152         ulk_t           ull_key;
 153         ull_lock_t      ull_lock;
 154         uint            ull_bucket_index;
 155         int32_t         ull_nwaiters;
 156         int32_t         ull_refcount;
 157         uint8_t         ull_opcode;
 158         struct turnstile *ull_turnstile;
 159         queue_chain_t   ull_hash_link;
 160 } ull_t;
 161
 162 extern void ulock_initialize(void);
 163
 164 #define ULL_MUST_EXIST  0x0001
 165 static void ull_put(ull_t *);
 166
 167 static uint32_t ulock_adaptive_spin_usecs = 20;
 168
 169 SYSCTL_INT(_kern, OID_AUTO, ulock_adaptive_spin_usecs, CTLFLAG_RW | CTLFLAG_LOCKED,
 170     &ulock_adaptive_spin_usecs, 0, "ulock adaptive spin duration");
 171
 172 #if DEVELOPMENT || DEBUG
 173 static int ull_simulate_copyin_fault = 0;
 174
 175 static void
 176 ull_dump(ull_t *ull)
 177 {
 178         kprintf("ull\t%p\n", ull);
 179         switch (ull->ull_key.ulk_key_type) {
 180         case ULK_UADDR:
 181                 kprintf("ull_key.ulk_key_type\tULK_UADDR\n");
 182                 kprintf("ull_key.ulk_pid\t%d\n", ull->ull_key.ulk_pid);
 183                 kprintf("ull_key.ulk_addr\t%p\n", (void *)(ull->ull_key.ulk_addr));
 184                 break;
 185         case ULK_XPROC:
 186                 kprintf("ull_key.ulk_key_type\tULK_XPROC\n");
 187                 kprintf("ull_key.ulk_object\t%p\n", (void *)(ull->ull_key.ulk_object));
 188                 kprintf("ull_key.ulk_offset\t%p\n", (void *)(ull->ull_key.ulk_offset));
 189                 break;
 190         default:
 191                 kprintf("ull_key.ulk_key_type\tUNKNOWN %d\n", ull->ull_key.ulk_key_type);
 192                 break;
 193         }
 194         kprintf("ull_nwaiters\t%d\n", ull->ull_nwaiters);
 195         kprintf("ull_refcount\t%d\n", ull->ull_refcount);
 196         kprintf("ull_opcode\t%d\n\n", ull->ull_opcode);
 197         kprintf("ull_owner\t0x%llx\n\n", thread_tid(ull->ull_owner));
 198         kprintf("ull_turnstile\t%p\n\n", ull->ull_turnstile);
 199 }
 200 #endif
 201
 202 typedef struct ull_bucket {
 203         queue_head_t ulb_head;
 204         lck_spin_t   ulb_lock;
 205 } ull_bucket_t;
 206
 207 static int ull_hash_buckets;
 208 static ull_bucket_t *ull_bucket;
 209 static uint32_t ull_nzalloc = 0;
 210 static zone_t ull_zone;
 211
 212 #define ull_bucket_lock(i)       lck_spin_lock_grp(&ull_bucket[i].ulb_lock, ull_lck_grp)
 213 #define ull_bucket_unlock(i)     lck_spin_unlock(&ull_bucket[i].ulb_lock)
 214
 215 static __inline__ uint32_t
 216 ull_hash_index(const void *key, size_t length)
 217 {
 218         uint32_t hash = os_hash_jenkins(key, length);
 219
 220         hash &= (ull_hash_buckets - 1);
 221
 222         return hash;
 223 }
 224
 225 #define ULL_INDEX(keyp) ull_hash_index(keyp, keyp->ulk_key_type == ULK_UADDR ? ULK_UADDR_LEN : ULK_XPROC_LEN)
 226
 227 void
 228 ulock_initialize(void)
 229 {
 230         ull_lck_grp = lck_grp_alloc_init("ulocks", NULL);
 231
 232         assert(thread_max > 16);
 233         /* Size ull_hash_buckets based on thread_max.
 234          * Round up to nearest power of 2, then divide by 4
 235          */
 236         ull_hash_buckets = (1 << (bit_ceiling(thread_max) - 2));
 237
 238         kprintf("%s>thread_max=%d, ull_hash_buckets=%d\n", __FUNCTION__, thread_max, ull_hash_buckets);
 239         assert(ull_hash_buckets >= thread_max / 4);
 240
 241         ull_bucket = (ull_bucket_t *)kalloc(sizeof(ull_bucket_t) * ull_hash_buckets);
 242         assert(ull_bucket != NULL);
 243
 244         for (int i = 0; i < ull_hash_buckets; i++) {
 245                 queue_init(&ull_bucket[i].ulb_head);
 246                 lck_spin_init(&ull_bucket[i].ulb_lock, ull_lck_grp, NULL);
 247         }
 248
 249         ull_zone = zinit(sizeof(ull_t),
 250             thread_max * sizeof(ull_t),
 251             0, "ulocks");
 252
 253         zone_change(ull_zone, Z_NOENCRYPT, TRUE);
 254         zone_change(ull_zone, Z_CACHING_ENABLED, TRUE);
 255 }
 256
 257 #if DEVELOPMENT || DEBUG
 258 /* Count the number of hash entries for a given pid.
 259  * if pid==0, dump the whole table.
 260  */
 261 static int
 262 ull_hash_dump(pid_t pid)
 263 {
 264         int count = 0;
 265         if (pid == 0) {
 266                 kprintf("%s>total number of ull_t allocated %d\n", __FUNCTION__, ull_nzalloc);
 267                 kprintf("%s>BEGIN\n", __FUNCTION__);
 268         }
 269         for (int i = 0; i < ull_hash_buckets; i++) {
 270                 ull_bucket_lock(i);
 271                 if (!queue_empty(&ull_bucket[i].ulb_head)) {
 272                         ull_t *elem;
 273                         if (pid == 0) {
 274                                 kprintf("%s>index %d:\n", __FUNCTION__, i);
 275                         }
 276                         qe_foreach_element(elem, &ull_bucket[i].ulb_head, ull_hash_link) {
 277                                 if ((pid == 0) || ((elem->ull_key.ulk_key_type == ULK_UADDR) && (pid == elem->ull_key.ulk_pid))) {
 278                                         ull_dump(elem);
 279                                         count++;
 280                                 }
 281                         }
 282                 }
 283                 ull_bucket_unlock(i);
 284         }
 285         if (pid == 0) {
 286                 kprintf("%s>END\n", __FUNCTION__);
 287                 ull_nzalloc = 0;
 288         }
 289         return count;
 290 }
 291 #endif
 292
 293 static ull_t *
 294 ull_alloc(ulk_t *key)
 295 {
 296         ull_t *ull = (ull_t *)zalloc(ull_zone);
 297         assert(ull != NULL);
 298
 299         ull->ull_refcount = 1;
 300         ull->ull_key = *key;
 301         ull->ull_bucket_index = ULL_INDEX(key);
 302         ull->ull_nwaiters = 0;
 303         ull->ull_opcode = 0;
 304
 305         ull->ull_owner = THREAD_NULL;
 306         ull->ull_turnstile = TURNSTILE_NULL;
 307
 308         ull_lock_init(ull);
 309
 310         ull_nzalloc++;
 311         return ull;
 312 }
 313
 314 static void
 315 ull_free(ull_t *ull)
 316 {
 317         assert(ull->ull_owner == THREAD_NULL);
 318         assert(ull->ull_turnstile == TURNSTILE_NULL);
 319
 320         ull_assert_notwned(ull);
 321
 322         ull_lock_destroy(ull);
 323
 324         zfree(ull_zone, ull);
 325 }
 326
 327 /* Finds an existing ulock structure (ull_t), or creates a new one.
 328  * If MUST_EXIST flag is set, returns NULL instead of creating a new one.
 329  * The ulock structure is returned with ull_lock locked
 330  */
 331 static ull_t *
 332 ull_get(ulk_t *key, uint32_t flags, ull_t **unused_ull)
 333 {
 334         ull_t *ull = NULL;
 335         uint i = ULL_INDEX(key);
 336         ull_t *new_ull = (flags & ULL_MUST_EXIST) ? NULL : ull_alloc(key);
 337         ull_t *elem;
 338
 339         ull_bucket_lock(i);
 340         qe_foreach_element(elem, &ull_bucket[i].ulb_head, ull_hash_link) {
 341                 ull_lock(elem);
 342                 if (ull_key_match(&elem->ull_key, key)) {
 343                         ull = elem;
 344                         break;
 345                 } else {
 346                         ull_unlock(elem);
 347                 }
 348         }
 349         if (ull == NULL) {
 350                 if (flags & ULL_MUST_EXIST) {
 351                         /* Must already exist (called from wake) */
 352                         ull_bucket_unlock(i);
 353                         assert(new_ull == NULL);
 354                         assert(unused_ull == NULL);
 355                         return NULL;
 356                 }
 357
 358                 if (new_ull == NULL) {
 359                         /* Alloc above failed */
 360                         ull_bucket_unlock(i);
 361                         return NULL;
 362                 }
 363
 364                 ull = new_ull;
 365                 ull_lock(ull);
 366                 enqueue(&ull_bucket[i].ulb_head, &ull->ull_hash_link);
 367         } else if (!(flags & ULL_MUST_EXIST)) {
 368                 assert(new_ull);
 369                 assert(unused_ull);
 370                 assert(*unused_ull == NULL);
 371                 *unused_ull = new_ull;
 372         }
 373
 374         ull->ull_refcount++;
 375
 376         ull_bucket_unlock(i);
 377
 378         return ull; /* still locked */
 379 }
 380
 381 /*
 382  * Must be called with ull_lock held
 383  */
 384 static void
 385 ull_put(ull_t *ull)
 386 {
 387         ull_assert_owned(ull);
 388         int refcount = --ull->ull_refcount;
 389         assert(refcount == 0 ? (ull->ull_key.ulk_key_type == ULK_INVALID) : 1);
 390         ull_unlock(ull);
 391
 392         if (refcount > 0) {
 393                 return;
 394         }
 395
 396         ull_bucket_lock(ull->ull_bucket_index);
 397         remqueue(&ull->ull_hash_link);
 398         ull_bucket_unlock(ull->ull_bucket_index);
 399
 400         ull_free(ull);
 401 }
 402
 403 extern kern_return_t vm_map_page_info(vm_map_t map, vm_map_offset_t offset, vm_page_info_flavor_t flavor, vm_page_info_t info, mach_msg_type_number_t *count);
 404 extern vm_map_t current_map(void);
 405 extern boolean_t machine_thread_on_core(thread_t thread);
 406
 407 static int
 408 uaddr_findobj(user_addr_t uaddr, uint64_t *objectp, uint64_t *offsetp)
 409 {
 410         kern_return_t ret;
 411         vm_page_info_basic_data_t info;
 412         mach_msg_type_number_t count = VM_PAGE_INFO_BASIC_COUNT;
 413         ret = vm_map_page_info(current_map(), uaddr, VM_PAGE_INFO_BASIC, (vm_page_info_t)&info, &count);
 414         if (ret != KERN_SUCCESS) {
 415                 return EINVAL;
 416         }
 417
 418         if (objectp != NULL) {
 419                 *objectp = (uint64_t)info.object_id;
 420         }
 421         if (offsetp != NULL) {
 422                 *offsetp = (uint64_t)info.offset;
 423         }
 424
 425         return 0;
 426 }
 427
 428 static void ulock_wait_continue(void *, wait_result_t);
 429 static void ulock_wait_cleanup(ull_t *, thread_t, thread_t, int32_t *);
 430
 431 inline static int
 432 wait_result_to_return_code(wait_result_t wr)
 433 {
 434         int ret = 0;
 435
 436         switch (wr) {
 437         case THREAD_AWAKENED:
 438                 break;
 439         case THREAD_TIMED_OUT:
 440                 ret = ETIMEDOUT;
 441                 break;
 442         case THREAD_INTERRUPTED:
 443         case THREAD_RESTART:
 444         default:
 445                 ret = EINTR;
 446                 break;
 447         }
 448
 449         return ret;
 450 }
 451
 452 static int
 453 ulock_resolve_owner(uint32_t value, thread_t *owner)
 454 {
 455         mach_port_name_t owner_name = ulock_owner_value_to_port_name(value);
 456
 457         *owner = port_name_to_thread(owner_name,
 458             PORT_TO_THREAD_IN_CURRENT_TASK |
 459             PORT_TO_THREAD_NOT_CURRENT_THREAD);
 460         if (*owner == THREAD_NULL) {
 461                 /*
 462                  * Translation failed - even though the lock value is up to date,
 463                  * whatever was stored in the lock wasn't actually a thread port.
 464                  */
 465                 return owner_name == MACH_PORT_DEAD ? ESRCH : EOWNERDEAD;
 466         }
 467         return 0;
 468 }
 469
 470 int
 471 ulock_wait(struct proc *p, struct ulock_wait_args *args, int32_t *retval)
 472 {
 473         uint opcode = args->operation & UL_OPCODE_MASK;
 474         uint flags = args->operation & UL_FLAGS_MASK;
 475
 476         if (flags & ULF_WAIT_CANCEL_POINT) {
 477                 __pthread_testcancel(1);
 478         }
 479
 480         int ret = 0;
 481         thread_t self = current_thread();
 482         ulk_t key;
 483
 484         /* involved threads - each variable holds +1 ref if not null */
 485         thread_t owner_thread   = THREAD_NULL;
 486         thread_t old_owner      = THREAD_NULL;
 487
 488         ull_t *unused_ull = NULL;
 489
 490         if ((flags & ULF_WAIT_MASK) != flags) {
 491                 ret = EINVAL;
 492                 goto munge_retval;
 493         }
 494
 495         bool set_owner = false;
 496         bool xproc = false;
 497         size_t lock_size = sizeof(uint32_t);
 498         int copy_ret;
 499
 500         switch (opcode) {
 501         case UL_UNFAIR_LOCK:
 502                 set_owner = true;
 503                 break;
 504         case UL_COMPARE_AND_WAIT:
 505                 break;
 506         case UL_COMPARE_AND_WAIT64:
 507                 lock_size = sizeof(uint64_t);
 508                 break;
 509         case UL_COMPARE_AND_WAIT_SHARED:
 510                 xproc = true;
 511                 break;
 512         case UL_COMPARE_AND_WAIT64_SHARED:
 513                 xproc = true;
 514                 lock_size = sizeof(uint64_t);
 515                 break;
 516         default:
 517                 ret = EINVAL;
 518                 goto munge_retval;
 519         }
 520
 521         uint64_t value = 0;
 522
 523         if ((args->addr == 0) || (args->addr & (lock_size - 1))) {
 524                 ret = EINVAL;
 525                 goto munge_retval;
 526         }
 527
 528         if (xproc) {
 529                 uint64_t object = 0;
 530                 uint64_t offset = 0;
 531
 532                 ret = uaddr_findobj(args->addr, &object, &offset);
 533                 if (ret) {
 534                         ret = EINVAL;
 535                         goto munge_retval;
 536                 }
 537                 key.ulk_key_type = ULK_XPROC;
 538                 key.ulk_object = object;
 539                 key.ulk_offset = offset;
 540         } else {
 541                 key.ulk_key_type = ULK_UADDR;
 542                 key.ulk_pid = p->p_pid;
 543                 key.ulk_addr = args->addr;
 544         }
 545
 546         if ((flags & ULF_WAIT_ADAPTIVE_SPIN) && set_owner) {
 547                 /*
 548                  * Attempt the copyin outside of the lock once,
 549                  *
 550                  * If it doesn't match (which is common), return right away.
 551                  *
 552                  * If it matches, resolve the current owner, and if it is on core,
 553                  * spin a bit waiting for the value to change. If the owner isn't on
 554                  * core, or if the value stays stable, then go on with the regular
 555                  * blocking code.
 556                  */
 557                 uint64_t end = 0;
 558                 uint32_t u32;
 559
 560                 ret = copyin_atomic32(args->addr, &u32);
 561                 if (ret || u32 != args->value) {
 562                         goto munge_retval;
 563                 }
 564                 for (;;) {
 565                         if (owner_thread == NULL && ulock_resolve_owner(u32, &owner_thread) != 0) {
 566                                 break;
 567                         }
 568
 569                         /* owner_thread may have a +1 starting here */
 570
 571                         if (!machine_thread_on_core(owner_thread)) {
 572                                 break;
 573                         }
 574                         if (end == 0) {
 575                                 clock_interval_to_deadline(ulock_adaptive_spin_usecs,
 576                                     NSEC_PER_USEC, &end);
 577                         } else if (mach_absolute_time() > end) {
 578                                 break;
 579                         }
 580                         if (copyin_atomic32_wait_if_equals(args->addr, u32) != 0) {
 581                                 goto munge_retval;
 582                         }
 583                 }
 584         }
 585
 586         ull_t *ull = ull_get(&key, 0, &unused_ull);
 587         if (ull == NULL) {
 588                 ret = ENOMEM;
 589                 goto munge_retval;
 590         }
 591         /* ull is locked */
 592
 593         ull->ull_nwaiters++;
 594
 595         if (ull->ull_opcode == 0) {
 596                 ull->ull_opcode = opcode;
 597         } else if (ull->ull_opcode != opcode) {
 598                 ret = EDOM;
 599                 goto out_locked;
 600         }
 601
 602         /*
 603          * We don't want this copyin to get wedged behind VM operations,
 604          * but we have to read the userspace value under the ull lock for correctness.
 605          *
 606          * Until <rdar://problem/24999882> exists,
 607          * holding the ull spinlock across copyin forces any
 608          * vm_fault we encounter to fail.
 609          */
 610
 611         /* copyin_atomicXX always checks alignment */
 612
 613         if (lock_size == 4) {
 614                 uint32_t u32;
 615                 copy_ret = copyin_atomic32(args->addr, &u32);
 616                 value = u32;
 617         } else {
 618                 copy_ret = copyin_atomic64(args->addr, &value);
 619         }
 620
 621 #if DEVELOPMENT || DEBUG
 622         /* Occasionally simulate copyin finding the user address paged out */
 623         if (((ull_simulate_copyin_fault == p->p_pid) || (ull_simulate_copyin_fault == 1)) && (copy_ret == 0)) {
 624                 static _Atomic int fault_inject = 0;
 625                 if (os_atomic_inc_orig(&fault_inject, relaxed) % 73 == 0) {
 626                         copy_ret = EFAULT;
 627                 }
 628         }
 629 #endif
 630         if (copy_ret != 0) {
 631                 /* copyin() will return an error if the access to the user addr would have faulted,
 632                  * so just return and let the user level code fault it in.
 633                  */
 634                 ret = copy_ret;
 635                 goto out_locked;
 636         }
 637
 638         if (value != args->value) {
 639                 /* Lock value has changed from expected so bail out */
 640                 goto out_locked;
 641         }
 642
 643         if (set_owner) {
 644                 if (owner_thread == THREAD_NULL) {
 645                         ret = ulock_resolve_owner(args->value, &owner_thread);
 646                         if (ret == EOWNERDEAD) {
 647                                 /*
 648                                  * Translation failed - even though the lock value is up to date,
 649                                  * whatever was stored in the lock wasn't actually a thread port.
 650                                  */
 651                                 goto out_locked;
 652                         }
 653                         /* HACK: don't bail on MACH_PORT_DEAD, to avoid blowing up the no-tsd pthread lock */
 654                         ret = 0;
 655                 }
 656                 /* owner_thread has a +1 reference */
 657
 658                 /*
 659                  * At this point, I know:
 660                  * a) owner_thread is definitely the current owner, because I just read the value
 661                  * b) owner_thread is either:
 662                  *      i) holding the user lock or
 663                  *      ii) has just unlocked the user lock after I looked
 664                  *              and is heading toward the kernel to call ull_wake.
 665                  *              If so, it's going to have to wait for the ull mutex.
 666                  *
 667                  * Therefore, I can ask the turnstile to promote its priority, and I can rely
 668                  * on it to come by later to issue the wakeup and lose its promotion.
 669                  */
 670
 671                 /* Return the +1 ref from the ull_owner field */
 672                 old_owner = ull->ull_owner;
 673                 ull->ull_owner = THREAD_NULL;
 674
 675                 if (owner_thread != THREAD_NULL) {
 676                         /* The ull_owner field now owns a +1 ref on owner_thread */
 677                         thread_reference(owner_thread);
 678                         ull->ull_owner = owner_thread;
 679                 }
 680         }
 681
 682         wait_result_t wr;
 683         uint32_t timeout = args->timeout;
 684         uint64_t deadline = TIMEOUT_WAIT_FOREVER;
 685         wait_interrupt_t interruptible = THREAD_ABORTSAFE;
 686         struct turnstile *ts;
 687
 688         ts = turnstile_prepare((uintptr_t)ull, &ull->ull_turnstile,
 689             TURNSTILE_NULL, TURNSTILE_ULOCK);
 690         thread_set_pending_block_hint(self, kThreadWaitUserLock);
 691
 692         if (flags & ULF_WAIT_WORKQ_DATA_CONTENTION) {
 693                 interruptible |= THREAD_WAIT_NOREPORT;
 694         }
 695
 696         if (timeout) {
 697                 clock_interval_to_deadline(timeout, NSEC_PER_USEC, &deadline);
 698         }
 699
 700         turnstile_update_inheritor(ts, owner_thread,
 701             (TURNSTILE_DELAYED_UPDATE | TURNSTILE_INHERITOR_THREAD));
 702
 703         wr = waitq_assert_wait64(&ts->ts_waitq, CAST_EVENT64_T(ULOCK_TO_EVENT(ull)),
 704             interruptible, deadline);
 705
 706         ull_unlock(ull);
 707
 708         if (unused_ull) {
 709                 ull_free(unused_ull);
 710                 unused_ull = NULL;
 711         }
 712
 713         turnstile_update_inheritor_complete(ts, TURNSTILE_INTERLOCK_NOT_HELD);
 714
 715         if (wr == THREAD_WAITING) {
 716                 uthread_t uthread = (uthread_t)get_bsdthread_info(self);
 717                 uthread->uu_save.uus_ulock_wait_data.retval = retval;
 718                 uthread->uu_save.uus_ulock_wait_data.flags = flags;
 719                 uthread->uu_save.uus_ulock_wait_data.owner_thread = owner_thread;
 720                 uthread->uu_save.uus_ulock_wait_data.old_owner = old_owner;
 721                 if (set_owner && owner_thread != THREAD_NULL) {
 722                         thread_handoff_parameter(owner_thread, ulock_wait_continue, ull);
 723                 } else {
 724                         assert(owner_thread == THREAD_NULL);
 725                         thread_block_parameter(ulock_wait_continue, ull);
 726                 }
 727                 /* NOT REACHED */
 728         }
 729
 730         ret = wait_result_to_return_code(wr);
 731
 732         ull_lock(ull);
 733         turnstile_complete((uintptr_t)ull, &ull->ull_turnstile, NULL, TURNSTILE_ULOCK);
 734
 735 out_locked:
 736         ulock_wait_cleanup(ull, owner_thread, old_owner, retval);
 737         owner_thread = NULL;
 738
 739         if (unused_ull) {
 740                 ull_free(unused_ull);
 741                 unused_ull = NULL;
 742         }
 743
 744         assert(*retval >= 0);
 745
 746 munge_retval:
 747         if (owner_thread) {
 748                 thread_deallocate(owner_thread);
 749         }
 750         if (ret == ESTALE) {
 751                 ret = 0;
 752         }
 753         if ((flags & ULF_NO_ERRNO) && (ret != 0)) {
 754                 *retval = -ret;
 755                 ret = 0;
 756         }
 757         return ret;
 758 }
 759
 760 /*
 761  * Must be called with ull_lock held
 762  */
 763 static void
 764 ulock_wait_cleanup(ull_t *ull, thread_t owner_thread, thread_t old_owner, int32_t *retval)
 765 {
 766         ull_assert_owned(ull);
 767
 768         thread_t old_lingering_owner = THREAD_NULL;
 769
 770         *retval = --ull->ull_nwaiters;
 771         if (ull->ull_nwaiters == 0) {
 772                 /*
 773                  * If the wait was canceled early, we might need to
 774                  * clear out the lingering owner reference before
 775                  * freeing the ull.
 776                  */
 777                 old_lingering_owner = ull->ull_owner;
 778                 ull->ull_owner = THREAD_NULL;
 779
 780                 memset(&ull->ull_key, 0, sizeof ull->ull_key);
 781                 ull->ull_refcount--;
 782                 assert(ull->ull_refcount > 0);
 783         }
 784         ull_put(ull);
 785
 786         /* Need to be called after dropping the interlock */
 787         turnstile_cleanup();
 788
 789         if (owner_thread != THREAD_NULL) {
 790                 thread_deallocate(owner_thread);
 791         }
 792
 793         if (old_owner != THREAD_NULL) {
 794                 thread_deallocate(old_owner);
 795         }
 796
 797         if (old_lingering_owner != THREAD_NULL) {
 798                 thread_deallocate(old_lingering_owner);
 799         }
 800
 801         assert(*retval >= 0);
 802 }
 803
 804 __attribute__((noreturn))
 805 static void
 806 ulock_wait_continue(void * parameter, wait_result_t wr)
 807 {
 808         thread_t self = current_thread();
 809         uthread_t uthread = (uthread_t)get_bsdthread_info(self);
 810         int ret = 0;
 811
 812         ull_t *ull = (ull_t *)parameter;
 813         int32_t *retval = uthread->uu_save.uus_ulock_wait_data.retval;
 814         uint flags = uthread->uu_save.uus_ulock_wait_data.flags;
 815         thread_t owner_thread = uthread->uu_save.uus_ulock_wait_data.owner_thread;
 816         thread_t old_owner = uthread->uu_save.uus_ulock_wait_data.old_owner;
 817
 818         ret = wait_result_to_return_code(wr);
 819
 820         ull_lock(ull);
 821         turnstile_complete((uintptr_t)ull, &ull->ull_turnstile, NULL, TURNSTILE_ULOCK);
 822
 823         ulock_wait_cleanup(ull, owner_thread, old_owner, retval);
 824
 825         if ((flags & ULF_NO_ERRNO) && (ret != 0)) {
 826                 *retval = -ret;
 827                 ret = 0;
 828         }
 829
 830         unix_syscall_return(ret);
 831 }
 832
 833 int
 834 ulock_wake(struct proc *p, struct ulock_wake_args *args, __unused int32_t *retval)
 835 {
 836         uint opcode = args->operation & UL_OPCODE_MASK;
 837         uint flags = args->operation & UL_FLAGS_MASK;
 838         int ret = 0;
 839         ulk_t key;
 840
 841         /* involved threads - each variable holds +1 ref if not null */
 842         thread_t wake_thread    = THREAD_NULL;
 843
 844 #if DEVELOPMENT || DEBUG
 845         if (opcode == UL_DEBUG_HASH_DUMP_PID) {
 846                 *retval = ull_hash_dump(p->p_pid);
 847                 return ret;
 848         } else if (opcode == UL_DEBUG_HASH_DUMP_ALL) {
 849                 *retval = ull_hash_dump(0);
 850                 return ret;
 851         } else if (opcode == UL_DEBUG_SIMULATE_COPYIN_FAULT) {
 852                 ull_simulate_copyin_fault = (int)(args->wake_value);
 853                 return ret;
 854         }
 855 #endif
 856
 857         bool set_owner = false;
 858         bool xproc = false;
 859
 860         switch (opcode) {
 861         case UL_UNFAIR_LOCK:
 862                 set_owner = true;
 863                 break;
 864         case UL_COMPARE_AND_WAIT:
 865         case UL_COMPARE_AND_WAIT64:
 866                 break;
 867         case UL_COMPARE_AND_WAIT_SHARED:
 868         case UL_COMPARE_AND_WAIT64_SHARED:
 869                 xproc = true;
 870                 break;
 871         default:
 872                 ret = EINVAL;
 873                 goto munge_retval;
 874         }
 875
 876         if ((flags & ULF_WAKE_MASK) != flags) {
 877                 ret = EINVAL;
 878                 goto munge_retval;
 879         }
 880
 881         if ((flags & ULF_WAKE_THREAD) && ((flags & ULF_WAKE_ALL) || set_owner)) {
 882                 ret = EINVAL;
 883                 goto munge_retval;
 884         }
 885
 886         if (args->addr == 0) {
 887                 ret = EINVAL;
 888                 goto munge_retval;
 889         }
 890
 891         if (xproc) {
 892                 uint64_t object = 0;
 893                 uint64_t offset = 0;
 894
 895                 ret = uaddr_findobj(args->addr, &object, &offset);
 896                 if (ret) {
 897                         ret = EINVAL;
 898                         goto munge_retval;
 899                 }
 900                 key.ulk_key_type = ULK_XPROC;
 901                 key.ulk_object = object;
 902                 key.ulk_offset = offset;
 903         } else {
 904                 key.ulk_key_type = ULK_UADDR;
 905                 key.ulk_pid = p->p_pid;
 906                 key.ulk_addr = args->addr;
 907         }
 908
 909         if (flags & ULF_WAKE_THREAD) {
 910                 mach_port_name_t wake_thread_name = (mach_port_name_t)(args->wake_value);
 911                 wake_thread = port_name_to_thread(wake_thread_name,
 912                     PORT_TO_THREAD_IN_CURRENT_TASK |
 913                     PORT_TO_THREAD_NOT_CURRENT_THREAD);
 914                 if (wake_thread == THREAD_NULL) {
 915                         ret = ESRCH;
 916                         goto munge_retval;
 917                 }
 918         }
 919
 920         ull_t *ull = ull_get(&key, ULL_MUST_EXIST, NULL);
 921         thread_t new_owner = THREAD_NULL;
 922         struct turnstile *ts = TURNSTILE_NULL;
 923         thread_t cleanup_thread = THREAD_NULL;
 924
 925         if (ull == NULL) {
 926                 ret = ENOENT;
 927                 goto munge_retval;
 928         }
 929         /* ull is locked */
 930
 931         if (opcode != ull->ull_opcode) {
 932                 ret = EDOM;
 933                 goto out_ull_put;
 934         }
 935
 936         if (set_owner) {
 937                 if (ull->ull_owner != current_thread()) {
 938                         /*
 939                          * If the current thread isn't the known owner,
 940                          * then this wake call was late to the party,
 941                          * and the kernel already knows who owns the lock.
 942                          *
 943                          * This current owner already knows the lock is contended
 944                          * and will redrive wakes, just bail out.
 945                          */
 946                         goto out_ull_put;
 947                 }
 948         } else {
 949                 assert(ull->ull_owner == THREAD_NULL);
 950         }
 951
 952         ts = turnstile_prepare((uintptr_t)ull, &ull->ull_turnstile,
 953             TURNSTILE_NULL, TURNSTILE_ULOCK);
 954         assert(ts != TURNSTILE_NULL);
 955
 956         if (flags & ULF_WAKE_THREAD) {
 957                 kern_return_t kr = waitq_wakeup64_thread(&ts->ts_waitq,
 958                     CAST_EVENT64_T(ULOCK_TO_EVENT(ull)),
 959                     wake_thread, THREAD_AWAKENED);
 960                 if (kr != KERN_SUCCESS) {
 961                         assert(kr == KERN_NOT_WAITING);
 962                         ret = EALREADY;
 963                 }
 964         } else if (flags & ULF_WAKE_ALL) {
 965                 if (set_owner) {
 966                         turnstile_update_inheritor(ts, THREAD_NULL,
 967                             TURNSTILE_IMMEDIATE_UPDATE | TURNSTILE_INHERITOR_THREAD);
 968                 }
 969                 waitq_wakeup64_all(&ts->ts_waitq, CAST_EVENT64_T(ULOCK_TO_EVENT(ull)),
 970                     THREAD_AWAKENED, 0);
 971         } else if (set_owner) {
 972                 /*
 973                  * The turnstile waitq is priority ordered,
 974                  * and will wake up the highest priority waiter
 975                  * and set it as the inheritor for us.
 976                  */
 977                 new_owner = waitq_wakeup64_identify(&ts->ts_waitq,
 978                     CAST_EVENT64_T(ULOCK_TO_EVENT(ull)),
 979                     THREAD_AWAKENED, WAITQ_PROMOTE_ON_WAKE);
 980         } else {
 981                 waitq_wakeup64_one(&ts->ts_waitq, CAST_EVENT64_T(ULOCK_TO_EVENT(ull)),
 982                     THREAD_AWAKENED, WAITQ_ALL_PRIORITIES);
 983         }
 984
 985         if (set_owner) {
 986                 turnstile_update_inheritor_complete(ts, TURNSTILE_INTERLOCK_HELD);
 987                 cleanup_thread = ull->ull_owner;
 988                 ull->ull_owner = new_owner;
 989         }
 990
 991         turnstile_complete((uintptr_t)ull, &ull->ull_turnstile, NULL, TURNSTILE_ULOCK);
 992
 993 out_ull_put:
 994         ull_put(ull);
 995
 996         if (ts != TURNSTILE_NULL) {
 997                 /* Need to be called after dropping the interlock */
 998                 turnstile_cleanup();
 999         }
1000
1001         if (cleanup_thread != THREAD_NULL) {
1002                 thread_deallocate(cleanup_thread);
1003         }
1004
1005 munge_retval:
1006         if (wake_thread != THREAD_NULL) {
1007                 thread_deallocate(wake_thread);
1008         }
1009
1010         if ((flags & ULF_NO_ERRNO) && (ret != 0)) {
1011                 *retval = -ret;
1012                 ret = 0;
1013         }
1014         return ret;
1015 }
1016
1017 void
1018 kdp_ulock_find_owner(__unused struct waitq * waitq, event64_t event, thread_waitinfo_t * waitinfo)
1019 {
1020         ull_t *ull = EVENT_TO_ULOCK(event);
1021         assert(kdp_is_in_zone(ull, "ulocks"));
1022
1023         switch (ull->ull_opcode) {
1024         case UL_UNFAIR_LOCK:
1025         case UL_UNFAIR_LOCK64_SHARED:
1026                 waitinfo->owner   = thread_tid(ull->ull_owner);
1027                 waitinfo->context = ull->ull_key.ulk_addr;
1028                 break;
1029         case UL_COMPARE_AND_WAIT:
1030         case UL_COMPARE_AND_WAIT64:
1031         case UL_COMPARE_AND_WAIT_SHARED:
1032         case UL_COMPARE_AND_WAIT64_SHARED:
1033                 waitinfo->owner   = 0;
1034                 waitinfo->context = ull->ull_key.ulk_addr;
1035                 break;
1036         default:
1037                 panic("%s: Invalid ulock opcode %d addr %p", __FUNCTION__, ull->ull_opcode, (void*)ull);
1038                 break;
1039         }
1040         return;
1041 }