sys/kern/kern_umtx.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2015, 2016 The FreeBSD Foundation
   5  * Copyright (c) 2004, David Xu <davidxu@freebsd.org>
   6  * Copyright (c) 2002, Jeffrey Roberson <jeff@freebsd.org>
   7  * All rights reserved.
   8  *
   9  * Portions of this software were developed by Konstantin Belousov
  10  * under sponsorship from the FreeBSD Foundation.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice unmodified, this list of conditions, and the following
  17  *    disclaimer.
  18  * 2. Redistributions in binary form must reproduce the above copyright
  19  *    notice, this list of conditions and the following disclaimer in the
  20  *    documentation and/or other materials provided with the distribution.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #include <sys/cdefs.h>
  35 __FBSDID("$FreeBSD$");
  36
  37 #include "opt_umtx_profiling.h"
  38
  39 #include <sys/param.h>
  40 #include <sys/kernel.h>
  41 #include <sys/fcntl.h>
  42 #include <sys/file.h>
  43 #include <sys/filedesc.h>
  44 #include <sys/limits.h>
  45 #include <sys/lock.h>
  46 #include <sys/malloc.h>
  47 #include <sys/mman.h>
  48 #include <sys/mutex.h>
  49 #include <sys/priv.h>
  50 #include <sys/proc.h>
  51 #include <sys/resource.h>
  52 #include <sys/resourcevar.h>
  53 #include <sys/rwlock.h>
  54 #include <sys/sbuf.h>
  55 #include <sys/sched.h>
  56 #include <sys/smp.h>
  57 #include <sys/sysctl.h>
  58 #include <sys/sysent.h>
  59 #include <sys/systm.h>
  60 #include <sys/sysproto.h>
  61 #include <sys/syscallsubr.h>
  62 #include <sys/taskqueue.h>
  63 #include <sys/time.h>
  64 #include <sys/eventhandler.h>
  65 #include <sys/umtx.h>
  66 #include <sys/umtxvar.h>
  67
  68 #include <security/mac/mac_framework.h>
  69
  70 #include <vm/vm.h>
  71 #include <vm/vm_param.h>
  72 #include <vm/pmap.h>
  73 #include <vm/vm_map.h>
  74 #include <vm/vm_object.h>
  75
  76 #include <machine/atomic.h>
  77 #include <machine/cpu.h>
  78
  79 #include <compat/freebsd32/freebsd32.h>
  80 #ifdef COMPAT_FREEBSD32
  81 #include <compat/freebsd32/freebsd32_proto.h>
  82 #endif
  83
  84 #define _UMUTEX_TRY             1
  85 #define _UMUTEX_WAIT            2
  86
  87 #ifdef UMTX_PROFILING
  88 #define UPROF_PERC_BIGGER(w, f, sw, sf)                                 \
  89         (((w) > (sw)) || ((w) == (sw) && (f) > (sf)))
  90 #endif
  91
  92 /* Priority inheritance mutex info. */
  93 struct umtx_pi {
  94         /* Owner thread */
  95         struct thread           *pi_owner;
  96
  97         /* Reference count */
  98         int                     pi_refcount;
  99
 100         /* List entry to link umtx holding by thread */
 101         TAILQ_ENTRY(umtx_pi)    pi_link;
 102
 103         /* List entry in hash */
 104         TAILQ_ENTRY(umtx_pi)    pi_hashlink;
 105
 106         /* List for waiters */
 107         TAILQ_HEAD(,umtx_q)     pi_blocked;
 108
 109         /* Identify a userland lock object */
 110         struct umtx_key         pi_key;
 111 };
 112
 113 /* A userland synchronous object user. */
 114 struct umtx_q {
 115         /* Linked list for the hash. */
 116         TAILQ_ENTRY(umtx_q)     uq_link;
 117
 118         /* Umtx key. */
 119         struct umtx_key         uq_key;
 120
 121         /* Umtx flags. */
 122         int                     uq_flags;
 123 #define UQF_UMTXQ       0x0001
 124
 125         /* The thread waits on. */
 126         struct thread           *uq_thread;
 127
 128         /*
 129          * Blocked on PI mutex. read can use chain lock
 130          * or umtx_lock, write must have both chain lock and
 131          * umtx_lock being hold.
 132          */
 133         struct umtx_pi          *uq_pi_blocked;
 134
 135         /* On blocked list */
 136         TAILQ_ENTRY(umtx_q)     uq_lockq;
 137
 138         /* Thread contending with us */
 139         TAILQ_HEAD(,umtx_pi)    uq_pi_contested;
 140
 141         /* Inherited priority from PP mutex */
 142         u_char                  uq_inherited_pri;
 143
 144         /* Spare queue ready to be reused */
 145         struct umtxq_queue      *uq_spare_queue;
 146
 147         /* The queue we on */
 148         struct umtxq_queue      *uq_cur_queue;
 149 };
 150
 151 TAILQ_HEAD(umtxq_head, umtx_q);
 152
 153 /* Per-key wait-queue */
 154 struct umtxq_queue {
 155         struct umtxq_head       head;
 156         struct umtx_key         key;
 157         LIST_ENTRY(umtxq_queue) link;
 158         int                     length;
 159 };
 160
 161 LIST_HEAD(umtxq_list, umtxq_queue);
 162
 163 /* Userland lock object's wait-queue chain */
 164 struct umtxq_chain {
 165         /* Lock for this chain. */
 166         struct mtx              uc_lock;
 167
 168         /* List of sleep queues. */
 169         struct umtxq_list       uc_queue[2];
 170 #define UMTX_SHARED_QUEUE       0
 171 #define UMTX_EXCLUSIVE_QUEUE    1
 172
 173         LIST_HEAD(, umtxq_queue) uc_spare_queue;
 174
 175         /* Busy flag */
 176         char                    uc_busy;
 177
 178         /* Chain lock waiters */
 179         int                     uc_waiters;
 180
 181         /* All PI in the list */
 182         TAILQ_HEAD(,umtx_pi)    uc_pi_list;
 183
 184 #ifdef UMTX_PROFILING
 185         u_int                   length;
 186         u_int                   max_length;
 187 #endif
 188 };
 189
 190 #define UMTXQ_LOCKED_ASSERT(uc)         mtx_assert(&(uc)->uc_lock, MA_OWNED)
 191
 192 /*
 193  * Don't propagate time-sharing priority, there is a security reason,
 194  * a user can simply introduce PI-mutex, let thread A lock the mutex,
 195  * and let another thread B block on the mutex, because B is
 196  * sleeping, its priority will be boosted, this causes A's priority to
 197  * be boosted via priority propagating too and will never be lowered even
 198  * if it is using 100%CPU, this is unfair to other processes.
 199  */
 200
 201 #define UPRI(td)        (((td)->td_user_pri >= PRI_MIN_TIMESHARE &&\
 202                           (td)->td_user_pri <= PRI_MAX_TIMESHARE) ?\
 203                          PRI_MAX_TIMESHARE : (td)->td_user_pri)
 204
 205 #define GOLDEN_RATIO_PRIME      2654404609U
 206 #ifndef UMTX_CHAINS
 207 #define UMTX_CHAINS             512
 208 #endif
 209 #define UMTX_SHIFTS             (__WORD_BIT - 9)
 210
 211 #define GET_SHARE(flags)        \
 212     (((flags) & USYNC_PROCESS_SHARED) == 0 ? THREAD_SHARE : PROCESS_SHARE)
 213
 214 #define BUSY_SPINS              200
 215
 216 struct abs_timeout {
 217         int clockid;
 218         bool is_abs_real;       /* TIMER_ABSTIME && CLOCK_REALTIME* */
 219         struct timespec cur;
 220         struct timespec end;
 221 };
 222
 223 struct umtx_copyops {
 224         int     (*copyin_timeout)(const void *uaddr, struct timespec *tsp);
 225         int     (*copyin_umtx_time)(const void *uaddr, size_t size,
 226             struct _umtx_time *tp);
 227         int     (*copyin_robust_lists)(const void *uaddr, size_t size,
 228             struct umtx_robust_lists_params *rbp);
 229         int     (*copyout_timeout)(void *uaddr, size_t size,
 230             struct timespec *tsp);
 231         const size_t    timespec_sz;
 232         const size_t    umtx_time_sz;
 233         const bool      compat32;
 234 };
 235
 236 _Static_assert(sizeof(struct umutex) == sizeof(struct umutex32), "umutex32");
 237 _Static_assert(__offsetof(struct umutex, m_spare[0]) ==
 238     __offsetof(struct umutex32, m_spare[0]), "m_spare32");
 239
 240 int umtx_shm_vnobj_persistent = 0;
 241 SYSCTL_INT(_kern_ipc, OID_AUTO, umtx_vnode_persistent, CTLFLAG_RWTUN,
 242     &umtx_shm_vnobj_persistent, 0,
 243     "False forces destruction of umtx attached to file, on last close");
 244 static int umtx_max_rb = 1000;
 245 SYSCTL_INT(_kern_ipc, OID_AUTO, umtx_max_robust, CTLFLAG_RWTUN,
 246     &umtx_max_rb, 0,
 247     "Maximum number of robust mutexes allowed for each thread");
 248
 249 static uma_zone_t               umtx_pi_zone;
 250 static struct umtxq_chain       umtxq_chains[2][UMTX_CHAINS];
 251 static MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory");
 252 static int                      umtx_pi_allocated;
 253
 254 static SYSCTL_NODE(_debug, OID_AUTO, umtx, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
 255     "umtx debug");
 256 SYSCTL_INT(_debug_umtx, OID_AUTO, umtx_pi_allocated, CTLFLAG_RD,
 257     &umtx_pi_allocated, 0, "Allocated umtx_pi");
 258 static int umtx_verbose_rb = 1;
 259 SYSCTL_INT(_debug_umtx, OID_AUTO, robust_faults_verbose, CTLFLAG_RWTUN,
 260     &umtx_verbose_rb, 0,
 261     "");
 262
 263 #ifdef UMTX_PROFILING
 264 static long max_length;
 265 SYSCTL_LONG(_debug_umtx, OID_AUTO, max_length, CTLFLAG_RD, &max_length, 0, "max_length");
 266 static SYSCTL_NODE(_debug_umtx, OID_AUTO, chains, CTLFLAG_RD | CTLFLAG_MPSAFE, 0,
 267     "umtx chain stats");
 268 #endif
 269
 270 static void abs_timeout_update(struct abs_timeout *timo);
 271
 272 static void umtx_shm_init(void);
 273 static void umtxq_sysinit(void *);
 274 static void umtxq_hash(struct umtx_key *key);
 275 static struct umtxq_chain *umtxq_getchain(struct umtx_key *key);
 276 static void umtxq_unlock(struct umtx_key *key);
 277 static void umtxq_busy(struct umtx_key *key);
 278 static void umtxq_unbusy(struct umtx_key *key);
 279 static void umtxq_insert_queue(struct umtx_q *uq, int q);
 280 static void umtxq_remove_queue(struct umtx_q *uq, int q);
 281 static int umtxq_sleep(struct umtx_q *uq, const char *wmesg, struct abs_timeout *);
 282 static int umtxq_count(struct umtx_key *key);
 283 static struct umtx_pi *umtx_pi_alloc(int);
 284 static void umtx_pi_free(struct umtx_pi *pi);
 285 static int do_unlock_pp(struct thread *td, struct umutex *m, uint32_t flags,
 286     bool rb);
 287 static void umtx_thread_cleanup(struct thread *td);
 288 SYSINIT(umtx, SI_SUB_EVENTHANDLER+1, SI_ORDER_MIDDLE, umtxq_sysinit, NULL);
 289
 290 #define umtxq_signal(key, nwake)        umtxq_signal_queue((key), (nwake), UMTX_SHARED_QUEUE)
 291 #define umtxq_insert(uq)        umtxq_insert_queue((uq), UMTX_SHARED_QUEUE)
 292 #define umtxq_remove(uq)        umtxq_remove_queue((uq), UMTX_SHARED_QUEUE)
 293
 294 static struct mtx umtx_lock;
 295
 296 #ifdef UMTX_PROFILING
 297 static void
 298 umtx_init_profiling(void)
 299 {
 300         struct sysctl_oid *chain_oid;
 301         char chain_name[10];
 302         int i;
 303
 304         for (i = 0; i < UMTX_CHAINS; ++i) {
 305                 snprintf(chain_name, sizeof(chain_name), "%d", i);
 306                 chain_oid = SYSCTL_ADD_NODE(NULL,
 307                     SYSCTL_STATIC_CHILDREN(_debug_umtx_chains), OID_AUTO,
 308                     chain_name, CTLFLAG_RD | CTLFLAG_MPSAFE, NULL,
 309                     "umtx hash stats");
 310                 SYSCTL_ADD_INT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO,
 311                     "max_length0", CTLFLAG_RD, &umtxq_chains[0][i].max_length, 0, NULL);
 312                 SYSCTL_ADD_INT(NULL, SYSCTL_CHILDREN(chain_oid), OID_AUTO,
 313                     "max_length1", CTLFLAG_RD, &umtxq_chains[1][i].max_length, 0, NULL);
 314         }
 315 }
 316
 317 static int
 318 sysctl_debug_umtx_chains_peaks(SYSCTL_HANDLER_ARGS)
 319 {
 320         char buf[512];
 321         struct sbuf sb;
 322         struct umtxq_chain *uc;
 323         u_int fract, i, j, tot, whole;
 324         u_int sf0, sf1, sf2, sf3, sf4;
 325         u_int si0, si1, si2, si3, si4;
 326         u_int sw0, sw1, sw2, sw3, sw4;
 327
 328         sbuf_new(&sb, buf, sizeof(buf), SBUF_FIXEDLEN);
 329         for (i = 0; i < 2; i++) {
 330                 tot = 0;
 331                 for (j = 0; j < UMTX_CHAINS; ++j) {
 332                         uc = &umtxq_chains[i][j];
 333                         mtx_lock(&uc->uc_lock);
 334                         tot += uc->max_length;
 335                         mtx_unlock(&uc->uc_lock);
 336                 }
 337                 if (tot == 0)
 338                         sbuf_printf(&sb, "%u) Empty ", i);
 339                 else {
 340                         sf0 = sf1 = sf2 = sf3 = sf4 = 0;
 341                         si0 = si1 = si2 = si3 = si4 = 0;
 342                         sw0 = sw1 = sw2 = sw3 = sw4 = 0;
 343                         for (j = 0; j < UMTX_CHAINS; j++) {
 344                                 uc = &umtxq_chains[i][j];
 345                                 mtx_lock(&uc->uc_lock);
 346                                 whole = uc->max_length * 100;
 347                                 mtx_unlock(&uc->uc_lock);
 348                                 fract = (whole % tot) * 100;
 349                                 if (UPROF_PERC_BIGGER(whole, fract, sw0, sf0)) {
 350                                         sf0 = fract;
 351                                         si0 = j;
 352                                         sw0 = whole;
 353                                 } else if (UPROF_PERC_BIGGER(whole, fract, sw1,
 354                                     sf1)) {
 355                                         sf1 = fract;
 356                                         si1 = j;
 357                                         sw1 = whole;
 358                                 } else if (UPROF_PERC_BIGGER(whole, fract, sw2,
 359                                     sf2)) {
 360                                         sf2 = fract;
 361                                         si2 = j;
 362                                         sw2 = whole;
 363                                 } else if (UPROF_PERC_BIGGER(whole, fract, sw3,
 364                                     sf3)) {
 365                                         sf3 = fract;
 366                                         si3 = j;
 367                                         sw3 = whole;
 368                                 } else if (UPROF_PERC_BIGGER(whole, fract, sw4,
 369                                     sf4)) {
 370                                         sf4 = fract;
 371                                         si4 = j;
 372                                         sw4 = whole;
 373                                 }
 374                         }
 375                         sbuf_printf(&sb, "queue %u:\n", i);
 376                         sbuf_printf(&sb, "1st: %u.%u%% idx: %u\n", sw0 / tot,
 377                             sf0 / tot, si0);
 378                         sbuf_printf(&sb, "2nd: %u.%u%% idx: %u\n", sw1 / tot,
 379                             sf1 / tot, si1);
 380                         sbuf_printf(&sb, "3rd: %u.%u%% idx: %u\n", sw2 / tot,
 381                             sf2 / tot, si2);
 382                         sbuf_printf(&sb, "4th: %u.%u%% idx: %u\n", sw3 / tot,
 383                             sf3 / tot, si3);
 384                         sbuf_printf(&sb, "5th: %u.%u%% idx: %u\n", sw4 / tot,
 385                             sf4 / tot, si4);
 386                 }
 387         }
 388         sbuf_trim(&sb);
 389         sbuf_finish(&sb);
 390         sysctl_handle_string(oidp, sbuf_data(&sb), sbuf_len(&sb), req);
 391         sbuf_delete(&sb);
 392         return (0);
 393 }
 394
 395 static int
 396 sysctl_debug_umtx_chains_clear(SYSCTL_HANDLER_ARGS)
 397 {
 398         struct umtxq_chain *uc;
 399         u_int i, j;
 400         int clear, error;
 401
 402         clear = 0;
 403         error = sysctl_handle_int(oidp, &clear, 0, req);
 404         if (error != 0 || req->newptr == NULL)
 405                 return (error);
 406
 407         if (clear != 0) {
 408                 for (i = 0; i < 2; ++i) {
 409                         for (j = 0; j < UMTX_CHAINS; ++j) {
 410                                 uc = &umtxq_chains[i][j];
 411                                 mtx_lock(&uc->uc_lock);
 412                                 uc->length = 0;
 413                                 uc->max_length = 0;
 414                                 mtx_unlock(&uc->uc_lock);
 415                         }
 416                 }
 417         }
 418         return (0);
 419 }
 420
 421 SYSCTL_PROC(_debug_umtx_chains, OID_AUTO, clear,
 422     CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, 0, 0,
 423     sysctl_debug_umtx_chains_clear, "I",
 424     "Clear umtx chains statistics");
 425 SYSCTL_PROC(_debug_umtx_chains, OID_AUTO, peaks,
 426     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, 0, 0,
 427     sysctl_debug_umtx_chains_peaks, "A",
 428     "Highest peaks in chains max length");
 429 #endif
 430
 431 static void
 432 umtxq_sysinit(void *arg __unused)
 433 {
 434         int i, j;
 435
 436         umtx_pi_zone = uma_zcreate("umtx pi", sizeof(struct umtx_pi),
 437                 NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
 438         for (i = 0; i < 2; ++i) {
 439                 for (j = 0; j < UMTX_CHAINS; ++j) {
 440                         mtx_init(&umtxq_chains[i][j].uc_lock, "umtxql", NULL,
 441                                  MTX_DEF | MTX_DUPOK);
 442                         LIST_INIT(&umtxq_chains[i][j].uc_queue[0]);
 443                         LIST_INIT(&umtxq_chains[i][j].uc_queue[1]);
 444                         LIST_INIT(&umtxq_chains[i][j].uc_spare_queue);
 445                         TAILQ_INIT(&umtxq_chains[i][j].uc_pi_list);
 446                         umtxq_chains[i][j].uc_busy = 0;
 447                         umtxq_chains[i][j].uc_waiters = 0;
 448 #ifdef UMTX_PROFILING
 449                         umtxq_chains[i][j].length = 0;
 450                         umtxq_chains[i][j].max_length = 0;
 451 #endif
 452                 }
 453         }
 454 #ifdef UMTX_PROFILING
 455         umtx_init_profiling();
 456 #endif
 457         mtx_init(&umtx_lock, "umtx lock", NULL, MTX_DEF);
 458         umtx_shm_init();
 459 }
 460
 461 struct umtx_q *
 462 umtxq_alloc(void)
 463 {
 464         struct umtx_q *uq;
 465
 466         uq = malloc(sizeof(struct umtx_q), M_UMTX, M_WAITOK | M_ZERO);
 467         uq->uq_spare_queue = malloc(sizeof(struct umtxq_queue), M_UMTX,
 468             M_WAITOK | M_ZERO);
 469         TAILQ_INIT(&uq->uq_spare_queue->head);
 470         TAILQ_INIT(&uq->uq_pi_contested);
 471         uq->uq_inherited_pri = PRI_MAX;
 472         return (uq);
 473 }
 474
 475 void
 476 umtxq_free(struct umtx_q *uq)
 477 {
 478
 479         MPASS(uq->uq_spare_queue != NULL);
 480         free(uq->uq_spare_queue, M_UMTX);
 481         free(uq, M_UMTX);
 482 }
 483
 484 static inline void
 485 umtxq_hash(struct umtx_key *key)
 486 {
 487         unsigned n;
 488
 489         n = (uintptr_t)key->info.both.a + key->info.both.b;
 490         key->hash = ((n * GOLDEN_RATIO_PRIME) >> UMTX_SHIFTS) % UMTX_CHAINS;
 491 }
 492
 493 static inline struct umtxq_chain *
 494 umtxq_getchain(struct umtx_key *key)
 495 {
 496
 497         if (key->type <= TYPE_SEM)
 498                 return (&umtxq_chains[1][key->hash]);
 499         return (&umtxq_chains[0][key->hash]);
 500 }
 501
 502 /*
 503  * Lock a chain.
 504  *
 505  * The code is a macro so that file/line information is taken from the caller.
 506  */
 507 #define umtxq_lock(key) do {            \
 508         struct umtx_key *_key = (key);  \
 509         struct umtxq_chain *_uc;        \
 510                                         \
 511         _uc = umtxq_getchain(_key);     \
 512         mtx_lock(&_uc->uc_lock);        \
 513 } while (0)
 514
 515 /*
 516  * Unlock a chain.
 517  */
 518 static inline void
 519 umtxq_unlock(struct umtx_key *key)
 520 {
 521         struct umtxq_chain *uc;
 522
 523         uc = umtxq_getchain(key);
 524         mtx_unlock(&uc->uc_lock);
 525 }
 526
 527 /*
 528  * Set chain to busy state when following operation
 529  * may be blocked (kernel mutex can not be used).
 530  */
 531 static inline void
 532 umtxq_busy(struct umtx_key *key)
 533 {
 534         struct umtxq_chain *uc;
 535
 536         uc = umtxq_getchain(key);
 537         mtx_assert(&uc->uc_lock, MA_OWNED);
 538         if (uc->uc_busy) {
 539 #ifdef SMP
 540                 if (smp_cpus > 1) {
 541                         int count = BUSY_SPINS;
 542                         if (count > 0) {
 543                                 umtxq_unlock(key);
 544                                 while (uc->uc_busy && --count > 0)
 545                                         cpu_spinwait();
 546                                 umtxq_lock(key);
 547                         }
 548                 }
 549 #endif
 550                 while (uc->uc_busy) {
 551                         uc->uc_waiters++;
 552                         msleep(uc, &uc->uc_lock, 0, "umtxqb", 0);
 553                         uc->uc_waiters--;
 554                 }
 555         }
 556         uc->uc_busy = 1;
 557 }
 558
 559 /*
 560  * Unbusy a chain.
 561  */
 562 static inline void
 563 umtxq_unbusy(struct umtx_key *key)
 564 {
 565         struct umtxq_chain *uc;
 566
 567         uc = umtxq_getchain(key);
 568         mtx_assert(&uc->uc_lock, MA_OWNED);
 569         KASSERT(uc->uc_busy != 0, ("not busy"));
 570         uc->uc_busy = 0;
 571         if (uc->uc_waiters)
 572                 wakeup_one(uc);
 573 }
 574
 575 static inline void
 576 umtxq_unbusy_unlocked(struct umtx_key *key)
 577 {
 578
 579         umtxq_lock(key);
 580         umtxq_unbusy(key);
 581         umtxq_unlock(key);
 582 }
 583
 584 static struct umtxq_queue *
 585 umtxq_queue_lookup(struct umtx_key *key, int q)
 586 {
 587         struct umtxq_queue *uh;
 588         struct umtxq_chain *uc;
 589
 590         uc = umtxq_getchain(key);
 591         UMTXQ_LOCKED_ASSERT(uc);
 592         LIST_FOREACH(uh, &uc->uc_queue[q], link) {
 593                 if (umtx_key_match(&uh->key, key))
 594                         return (uh);
 595         }
 596
 597         return (NULL);
 598 }
 599
 600 static inline void
 601 umtxq_insert_queue(struct umtx_q *uq, int q)
 602 {
 603         struct umtxq_queue *uh;
 604         struct umtxq_chain *uc;
 605
 606         uc = umtxq_getchain(&uq->uq_key);
 607         UMTXQ_LOCKED_ASSERT(uc);
 608         KASSERT((uq->uq_flags & UQF_UMTXQ) == 0, ("umtx_q is already on queue"));
 609         uh = umtxq_queue_lookup(&uq->uq_key, q);
 610         if (uh != NULL) {
 611                 LIST_INSERT_HEAD(&uc->uc_spare_queue, uq->uq_spare_queue, link);
 612         } else {
 613                 uh = uq->uq_spare_queue;
 614                 uh->key = uq->uq_key;
 615                 LIST_INSERT_HEAD(&uc->uc_queue[q], uh, link);
 616 #ifdef UMTX_PROFILING
 617                 uc->length++;
 618                 if (uc->length > uc->max_length) {
 619                         uc->max_length = uc->length;
 620                         if (uc->max_length > max_length)
 621                                 max_length = uc->max_length;
 622                 }
 623 #endif
 624         }
 625         uq->uq_spare_queue = NULL;
 626
 627         TAILQ_INSERT_TAIL(&uh->head, uq, uq_link);
 628         uh->length++;
 629         uq->uq_flags |= UQF_UMTXQ;
 630         uq->uq_cur_queue = uh;
 631         return;
 632 }
 633
 634 static inline void
 635 umtxq_remove_queue(struct umtx_q *uq, int q)
 636 {
 637         struct umtxq_chain *uc;
 638         struct umtxq_queue *uh;
 639
 640         uc = umtxq_getchain(&uq->uq_key);
 641         UMTXQ_LOCKED_ASSERT(uc);
 642         if (uq->uq_flags & UQF_UMTXQ) {
 643                 uh = uq->uq_cur_queue;
 644                 TAILQ_REMOVE(&uh->head, uq, uq_link);
 645                 uh->length--;
 646                 uq->uq_flags &= ~UQF_UMTXQ;
 647                 if (TAILQ_EMPTY(&uh->head)) {
 648                         KASSERT(uh->length == 0,
 649                             ("inconsistent umtxq_queue length"));
 650 #ifdef UMTX_PROFILING
 651                         uc->length--;
 652 #endif
 653                         LIST_REMOVE(uh, link);
 654                 } else {
 655                         uh = LIST_FIRST(&uc->uc_spare_queue);
 656                         KASSERT(uh != NULL, ("uc_spare_queue is empty"));
 657                         LIST_REMOVE(uh, link);
 658                 }
 659                 uq->uq_spare_queue = uh;
 660                 uq->uq_cur_queue = NULL;
 661         }
 662 }
 663
 664 /*
 665  * Check if there are multiple waiters
 666  */
 667 static int
 668 umtxq_count(struct umtx_key *key)
 669 {
 670         struct umtxq_queue *uh;
 671
 672         UMTXQ_LOCKED_ASSERT(umtxq_getchain(key));
 673         uh = umtxq_queue_lookup(key, UMTX_SHARED_QUEUE);
 674         if (uh != NULL)
 675                 return (uh->length);
 676         return (0);
 677 }
 678
 679 /*
 680  * Check if there are multiple PI waiters and returns first
 681  * waiter.
 682  */
 683 static int
 684 umtxq_count_pi(struct umtx_key *key, struct umtx_q **first)
 685 {
 686         struct umtxq_queue *uh;
 687
 688         *first = NULL;
 689         UMTXQ_LOCKED_ASSERT(umtxq_getchain(key));
 690         uh = umtxq_queue_lookup(key, UMTX_SHARED_QUEUE);
 691         if (uh != NULL) {
 692                 *first = TAILQ_FIRST(&uh->head);
 693                 return (uh->length);
 694         }
 695         return (0);
 696 }
 697
 698 /*
 699  * Wake up threads waiting on an userland object.
 700  */
 701
 702 static int
 703 umtxq_signal_queue(struct umtx_key *key, int n_wake, int q)
 704 {
 705         struct umtxq_queue *uh;
 706         struct umtx_q *uq;
 707         int ret;
 708
 709         ret = 0;
 710         UMTXQ_LOCKED_ASSERT(umtxq_getchain(key));
 711         uh = umtxq_queue_lookup(key, q);
 712         if (uh != NULL) {
 713                 while ((uq = TAILQ_FIRST(&uh->head)) != NULL) {
 714                         umtxq_remove_queue(uq, q);
 715                         wakeup(uq);
 716                         if (++ret >= n_wake)
 717                                 return (ret);
 718                 }
 719         }
 720         return (ret);
 721 }
 722
 723 /*
 724  * Wake up specified thread.
 725  */
 726 static inline void
 727 umtxq_signal_thread(struct umtx_q *uq)
 728 {
 729
 730         UMTXQ_LOCKED_ASSERT(umtxq_getchain(&uq->uq_key));
 731         umtxq_remove(uq);
 732         wakeup(uq);
 733 }
 734
 735 static inline int
 736 tstohz(const struct timespec *tsp)
 737 {
 738         struct timeval tv;
 739
 740         TIMESPEC_TO_TIMEVAL(&tv, tsp);
 741         return tvtohz(&tv);
 742 }
 743
 744 static void
 745 abs_timeout_init(struct abs_timeout *timo, int clockid, int absolute,
 746         const struct timespec *timeout)
 747 {
 748
 749         timo->clockid = clockid;
 750         if (!absolute) {
 751                 timo->is_abs_real = false;
 752                 abs_timeout_update(timo);
 753                 timespecadd(&timo->cur, timeout, &timo->end);
 754         } else {
 755                 timo->end = *timeout;
 756                 timo->is_abs_real = clockid == CLOCK_REALTIME ||
 757                     clockid == CLOCK_REALTIME_FAST ||
 758                     clockid == CLOCK_REALTIME_PRECISE;
 759                 /*
 760                  * If is_abs_real, umtxq_sleep will read the clock
 761                  * after setting td_rtcgen; otherwise, read it here.
 762                  */
 763                 if (!timo->is_abs_real) {
 764                         abs_timeout_update(timo);
 765                 }
 766         }
 767 }
 768
 769 static void
 770 abs_timeout_init2(struct abs_timeout *timo, const struct _umtx_time *umtxtime)
 771 {
 772
 773         abs_timeout_init(timo, umtxtime->_clockid,
 774             (umtxtime->_flags & UMTX_ABSTIME) != 0, &umtxtime->_timeout);
 775 }
 776
 777 static inline void
 778 abs_timeout_update(struct abs_timeout *timo)
 779 {
 780
 781         kern_clock_gettime(curthread, timo->clockid, &timo->cur);
 782 }
 783
 784 static int
 785 abs_timeout_gethz(struct abs_timeout *timo)
 786 {
 787         struct timespec tts;
 788
 789         if (timespeccmp(&timo->end, &timo->cur, <=))
 790                 return (-1);
 791         timespecsub(&timo->end, &timo->cur, &tts);
 792         return (tstohz(&tts));
 793 }
 794
 795 static uint32_t
 796 umtx_unlock_val(uint32_t flags, bool rb)
 797 {
 798
 799         if (rb)
 800                 return (UMUTEX_RB_OWNERDEAD);
 801         else if ((flags & UMUTEX_NONCONSISTENT) != 0)
 802                 return (UMUTEX_RB_NOTRECOV);
 803         else
 804                 return (UMUTEX_UNOWNED);
 805
 806 }
 807
 808 /*
 809  * Put thread into sleep state, before sleeping, check if
 810  * thread was removed from umtx queue.
 811  */
 812 static inline int
 813 umtxq_sleep(struct umtx_q *uq, const char *wmesg, struct abs_timeout *abstime)
 814 {
 815         struct umtxq_chain *uc;
 816         int error, timo;
 817
 818         if (abstime != NULL && abstime->is_abs_real) {
 819                 curthread->td_rtcgen = atomic_load_acq_int(&rtc_generation);
 820                 abs_timeout_update(abstime);
 821         }
 822
 823         uc = umtxq_getchain(&uq->uq_key);
 824         UMTXQ_LOCKED_ASSERT(uc);
 825         for (;;) {
 826                 if (!(uq->uq_flags & UQF_UMTXQ)) {
 827                         error = 0;
 828                         break;
 829                 }
 830                 if (abstime != NULL) {
 831                         timo = abs_timeout_gethz(abstime);
 832                         if (timo < 0) {
 833                                 error = ETIMEDOUT;
 834                                 break;
 835                         }
 836                 } else
 837                         timo = 0;
 838                 error = msleep(uq, &uc->uc_lock, PCATCH | PDROP, wmesg, timo);
 839                 if (error == EINTR || error == ERESTART) {
 840                         umtxq_lock(&uq->uq_key);
 841                         break;
 842                 }
 843                 if (abstime != NULL) {
 844                         if (abstime->is_abs_real)
 845                                 curthread->td_rtcgen =
 846                                     atomic_load_acq_int(&rtc_generation);
 847                         abs_timeout_update(abstime);
 848                 }
 849                 umtxq_lock(&uq->uq_key);
 850         }
 851
 852         curthread->td_rtcgen = 0;
 853         return (error);
 854 }
 855
 856 /*
 857  * Convert userspace address into unique logical address.
 858  */
 859 int
 860 umtx_key_get(const void *addr, int type, int share, struct umtx_key *key)
 861 {
 862         struct thread *td = curthread;
 863         vm_map_t map;
 864         vm_map_entry_t entry;
 865         vm_pindex_t pindex;
 866         vm_prot_t prot;
 867         boolean_t wired;
 868
 869         key->type = type;
 870         if (share == THREAD_SHARE) {
 871                 key->shared = 0;
 872                 key->info.private.vs = td->td_proc->p_vmspace;
 873                 key->info.private.addr = (uintptr_t)addr;
 874         } else {
 875                 MPASS(share == PROCESS_SHARE || share == AUTO_SHARE);
 876                 map = &td->td_proc->p_vmspace->vm_map;
 877                 if (vm_map_lookup(&map, (vm_offset_t)addr, VM_PROT_WRITE,
 878                     &entry, &key->info.shared.object, &pindex, &prot,
 879                     &wired) != KERN_SUCCESS) {
 880                         return (EFAULT);
 881                 }
 882
 883                 if ((share == PROCESS_SHARE) ||
 884                     (share == AUTO_SHARE &&
 885                      VM_INHERIT_SHARE == entry->inheritance)) {
 886                         key->shared = 1;
 887                         key->info.shared.offset = (vm_offset_t)addr -
 888                             entry->start + entry->offset;
 889                         vm_object_reference(key->info.shared.object);
 890                 } else {
 891                         key->shared = 0;
 892                         key->info.private.vs = td->td_proc->p_vmspace;
 893                         key->info.private.addr = (uintptr_t)addr;
 894                 }
 895                 vm_map_lookup_done(map, entry);
 896         }
 897
 898         umtxq_hash(key);
 899         return (0);
 900 }
 901
 902 /*
 903  * Release key.
 904  */
 905 void
 906 umtx_key_release(struct umtx_key *key)
 907 {
 908         if (key->shared)
 909                 vm_object_deallocate(key->info.shared.object);
 910 }
 911
 912 #ifdef COMPAT_FREEBSD10
 913 /*
 914  * Lock a umtx object.
 915  */
 916 static int
 917 do_lock_umtx(struct thread *td, struct umtx *umtx, u_long id,
 918     const struct timespec *timeout)
 919 {
 920         struct abs_timeout timo;
 921         struct umtx_q *uq;
 922         u_long owner;
 923         u_long old;
 924         int error = 0;
 925
 926         uq = td->td_umtxq;
 927         if (timeout != NULL)
 928                 abs_timeout_init(&timo, CLOCK_REALTIME, 0, timeout);
 929
 930         /*
 931          * Care must be exercised when dealing with umtx structure. It
 932          * can fault on any access.
 933          */
 934         for (;;) {
 935                 /*
 936                  * Try the uncontested case.  This should be done in userland.
 937                  */
 938                 owner = casuword(&umtx->u_owner, UMTX_UNOWNED, id);
 939
 940                 /* The acquire succeeded. */
 941                 if (owner == UMTX_UNOWNED)
 942                         return (0);
 943
 944                 /* The address was invalid. */
 945                 if (owner == -1)
 946                         return (EFAULT);
 947
 948                 /* If no one owns it but it is contested try to acquire it. */
 949                 if (owner == UMTX_CONTESTED) {
 950                         owner = casuword(&umtx->u_owner,
 951                             UMTX_CONTESTED, id | UMTX_CONTESTED);
 952
 953                         if (owner == UMTX_CONTESTED)
 954                                 return (0);
 955
 956                         /* The address was invalid. */
 957                         if (owner == -1)
 958                                 return (EFAULT);
 959
 960                         error = thread_check_susp(td, false);
 961                         if (error != 0)
 962                                 break;
 963
 964                         /* If this failed the lock has changed, restart. */
 965                         continue;
 966                 }
 967
 968                 /*
 969                  * If we caught a signal, we have retried and now
 970                  * exit immediately.
 971                  */
 972                 if (error != 0)
 973                         break;
 974
 975                 if ((error = umtx_key_get(umtx, TYPE_SIMPLE_LOCK,
 976                         AUTO_SHARE, &uq->uq_key)) != 0)
 977                         return (error);
 978
 979                 umtxq_lock(&uq->uq_key);
 980                 umtxq_busy(&uq->uq_key);
 981                 umtxq_insert(uq);
 982                 umtxq_unbusy(&uq->uq_key);
 983                 umtxq_unlock(&uq->uq_key);
 984
 985                 /*
 986                  * Set the contested bit so that a release in user space
 987                  * knows to use the system call for unlock.  If this fails
 988                  * either some one else has acquired the lock or it has been
 989                  * released.
 990                  */
 991                 old = casuword(&umtx->u_owner, owner, owner | UMTX_CONTESTED);
 992
 993                 /* The address was invalid. */
 994                 if (old == -1) {
 995                         umtxq_lock(&uq->uq_key);
 996                         umtxq_remove(uq);
 997                         umtxq_unlock(&uq->uq_key);
 998                         umtx_key_release(&uq->uq_key);
 999                         return (EFAULT);
1000                 }
1001
1002                 /*
1003                  * We set the contested bit, sleep. Otherwise the lock changed
1004                  * and we need to retry or we lost a race to the thread
1005                  * unlocking the umtx.
1006                  */
1007                 umtxq_lock(&uq->uq_key);
1008                 if (old == owner)
1009                         error = umtxq_sleep(uq, "umtx", timeout == NULL ? NULL :
1010                             &timo);
1011                 umtxq_remove(uq);
1012                 umtxq_unlock(&uq->uq_key);
1013                 umtx_key_release(&uq->uq_key);
1014
1015                 if (error == 0)
1016                         error = thread_check_susp(td, false);
1017         }
1018
1019         if (timeout == NULL) {
1020                 /* Mutex locking is restarted if it is interrupted. */
1021                 if (error == EINTR)
1022                         error = ERESTART;
1023         } else {
1024                 /* Timed-locking is not restarted. */
1025                 if (error == ERESTART)
1026                         error = EINTR;
1027         }
1028         return (error);
1029 }
1030
1031 /*
1032  * Unlock a umtx object.
1033  */
1034 static int
1035 do_unlock_umtx(struct thread *td, struct umtx *umtx, u_long id)
1036 {
1037         struct umtx_key key;
1038         u_long owner;
1039         u_long old;
1040         int error;
1041         int count;
1042
1043         /*
1044          * Make sure we own this mtx.
1045          */
1046         owner = fuword(__DEVOLATILE(u_long *, &umtx->u_owner));
1047         if (owner == -1)
1048                 return (EFAULT);
1049
1050         if ((owner & ~UMTX_CONTESTED) != id)
1051                 return (EPERM);
1052
1053         /* This should be done in userland */
1054         if ((owner & UMTX_CONTESTED) == 0) {
1055                 old = casuword(&umtx->u_owner, owner, UMTX_UNOWNED);
1056                 if (old == -1)
1057                         return (EFAULT);
1058                 if (old == owner)
1059                         return (0);
1060                 owner = old;
1061         }
1062
1063         /* We should only ever be in here for contested locks */
1064         if ((error = umtx_key_get(umtx, TYPE_SIMPLE_LOCK, AUTO_SHARE,
1065             &key)) != 0)
1066                 return (error);
1067
1068         umtxq_lock(&key);
1069         umtxq_busy(&key);
1070         count = umtxq_count(&key);
1071         umtxq_unlock(&key);
1072
1073         /*
1074          * When unlocking the umtx, it must be marked as unowned if
1075          * there is zero or one thread only waiting for it.
1076          * Otherwise, it must be marked as contested.
1077          */
1078         old = casuword(&umtx->u_owner, owner,
1079             count <= 1 ? UMTX_UNOWNED : UMTX_CONTESTED);
1080         umtxq_lock(&key);
1081         umtxq_signal(&key,1);
1082         umtxq_unbusy(&key);
1083         umtxq_unlock(&key);
1084         umtx_key_release(&key);
1085         if (old == -1)
1086                 return (EFAULT);
1087         if (old != owner)
1088                 return (EINVAL);
1089         return (0);
1090 }
1091
1092 #ifdef COMPAT_FREEBSD32
1093
1094 /*
1095  * Lock a umtx object.
1096  */
1097 static int
1098 do_lock_umtx32(struct thread *td, uint32_t *m, uint32_t id,
1099         const struct timespec *timeout)
1100 {
1101         struct abs_timeout timo;
1102         struct umtx_q *uq;
1103         uint32_t owner;
1104         uint32_t old;
1105         int error = 0;
1106
1107         uq = td->td_umtxq;
1108
1109         if (timeout != NULL)
1110                 abs_timeout_init(&timo, CLOCK_REALTIME, 0, timeout);
1111
1112         /*
1113          * Care must be exercised when dealing with umtx structure. It
1114          * can fault on any access.
1115          */
1116         for (;;) {
1117                 /*
1118                  * Try the uncontested case.  This should be done in userland.
1119                  */
1120                 owner = casuword32(m, UMUTEX_UNOWNED, id);
1121
1122                 /* The acquire succeeded. */
1123                 if (owner == UMUTEX_UNOWNED)
1124                         return (0);
1125
1126                 /* The address was invalid. */
1127                 if (owner == -1)
1128                         return (EFAULT);
1129
1130                 /* If no one owns it but it is contested try to acquire it. */
1131                 if (owner == UMUTEX_CONTESTED) {
1132                         owner = casuword32(m,
1133                             UMUTEX_CONTESTED, id | UMUTEX_CONTESTED);
1134                         if (owner == UMUTEX_CONTESTED)
1135                                 return (0);
1136
1137                         /* The address was invalid. */
1138                         if (owner == -1)
1139                                 return (EFAULT);
1140
1141                         error = thread_check_susp(td, false);
1142                         if (error != 0)
1143                                 break;
1144
1145                         /* If this failed the lock has changed, restart. */
1146                         continue;
1147                 }
1148
1149                 /*
1150                  * If we caught a signal, we have retried and now
1151                  * exit immediately.
1152                  */
1153                 if (error != 0)
1154                         return (error);
1155
1156                 if ((error = umtx_key_get(m, TYPE_SIMPLE_LOCK,
1157                         AUTO_SHARE, &uq->uq_key)) != 0)
1158                         return (error);
1159
1160                 umtxq_lock(&uq->uq_key);
1161                 umtxq_busy(&uq->uq_key);
1162                 umtxq_insert(uq);
1163                 umtxq_unbusy(&uq->uq_key);
1164                 umtxq_unlock(&uq->uq_key);
1165
1166                 /*
1167                  * Set the contested bit so that a release in user space
1168                  * knows to use the system call for unlock.  If this fails
1169                  * either some one else has acquired the lock or it has been
1170                  * released.
1171                  */
1172                 old = casuword32(m, owner, owner | UMUTEX_CONTESTED);
1173
1174                 /* The address was invalid. */
1175                 if (old == -1) {
1176                         umtxq_lock(&uq->uq_key);
1177                         umtxq_remove(uq);
1178                         umtxq_unlock(&uq->uq_key);
1179                         umtx_key_release(&uq->uq_key);
1180                         return (EFAULT);
1181                 }
1182
1183                 /*
1184                  * We set the contested bit, sleep. Otherwise the lock changed
1185                  * and we need to retry or we lost a race to the thread
1186                  * unlocking the umtx.
1187                  */
1188                 umtxq_lock(&uq->uq_key);
1189                 if (old == owner)
1190                         error = umtxq_sleep(uq, "umtx", timeout == NULL ?
1191                             NULL : &timo);
1192                 umtxq_remove(uq);
1193                 umtxq_unlock(&uq->uq_key);
1194                 umtx_key_release(&uq->uq_key);
1195
1196                 if (error == 0)
1197                         error = thread_check_susp(td, false);
1198         }
1199
1200         if (timeout == NULL) {
1201                 /* Mutex locking is restarted if it is interrupted. */
1202                 if (error == EINTR)
1203                         error = ERESTART;
1204         } else {
1205                 /* Timed-locking is not restarted. */
1206                 if (error == ERESTART)
1207                         error = EINTR;
1208         }
1209         return (error);
1210 }
1211
1212 /*
1213  * Unlock a umtx object.
1214  */
1215 static int
1216 do_unlock_umtx32(struct thread *td, uint32_t *m, uint32_t id)
1217 {
1218         struct umtx_key key;
1219         uint32_t owner;
1220         uint32_t old;
1221         int error;
1222         int count;
1223
1224         /*
1225          * Make sure we own this mtx.
1226          */
1227         owner = fuword32(m);
1228         if (owner == -1)
1229                 return (EFAULT);
1230
1231         if ((owner & ~UMUTEX_CONTESTED) != id)
1232                 return (EPERM);
1233
1234         /* This should be done in userland */
1235         if ((owner & UMUTEX_CONTESTED) == 0) {
1236                 old = casuword32(m, owner, UMUTEX_UNOWNED);
1237                 if (old == -1)
1238                         return (EFAULT);
1239                 if (old == owner)
1240                         return (0);
1241                 owner = old;
1242         }
1243
1244         /* We should only ever be in here for contested locks */
1245         if ((error = umtx_key_get(m, TYPE_SIMPLE_LOCK, AUTO_SHARE,
1246                 &key)) != 0)
1247                 return (error);
1248
1249         umtxq_lock(&key);
1250         umtxq_busy(&key);
1251         count = umtxq_count(&key);
1252         umtxq_unlock(&key);
1253
1254         /*
1255          * When unlocking the umtx, it must be marked as unowned if
1256          * there is zero or one thread only waiting for it.
1257          * Otherwise, it must be marked as contested.
1258          */
1259         old = casuword32(m, owner,
1260                 count <= 1 ? UMUTEX_UNOWNED : UMUTEX_CONTESTED);
1261         umtxq_lock(&key);
1262         umtxq_signal(&key,1);
1263         umtxq_unbusy(&key);
1264         umtxq_unlock(&key);
1265         umtx_key_release(&key);
1266         if (old == -1)
1267                 return (EFAULT);
1268         if (old != owner)
1269                 return (EINVAL);
1270         return (0);
1271 }
1272 #endif  /* COMPAT_FREEBSD32 */
1273 #endif  /* COMPAT_FREEBSD10 */
1274
1275 /*
1276  * Fetch and compare value, sleep on the address if value is not changed.
1277  */
1278 static int
1279 do_wait(struct thread *td, void *addr, u_long id,
1280     struct _umtx_time *timeout, int compat32, int is_private)
1281 {
1282         struct abs_timeout timo;
1283         struct umtx_q *uq;
1284         u_long tmp;
1285         uint32_t tmp32;
1286         int error = 0;
1287
1288         uq = td->td_umtxq;
1289         if ((error = umtx_key_get(addr, TYPE_SIMPLE_WAIT,
1290                 is_private ? THREAD_SHARE : AUTO_SHARE, &uq->uq_key)) != 0)
1291                 return (error);
1292
1293         if (timeout != NULL)
1294                 abs_timeout_init2(&timo, timeout);
1295
1296         umtxq_lock(&uq->uq_key);
1297         umtxq_insert(uq);
1298         umtxq_unlock(&uq->uq_key);
1299         if (compat32 == 0) {
1300                 error = fueword(addr, &tmp);
1301                 if (error != 0)
1302                         error = EFAULT;
1303         } else {
1304                 error = fueword32(addr, &tmp32);
1305                 if (error == 0)
1306                         tmp = tmp32;
1307                 else
1308                         error = EFAULT;
1309         }
1310         umtxq_lock(&uq->uq_key);
1311         if (error == 0) {
1312                 if (tmp == id)
1313                         error = umtxq_sleep(uq, "uwait", timeout == NULL ?
1314                             NULL : &timo);
1315                 if ((uq->uq_flags & UQF_UMTXQ) == 0)
1316                         error = 0;
1317                 else
1318                         umtxq_remove(uq);
1319         } else if ((uq->uq_flags & UQF_UMTXQ) != 0) {
1320                 umtxq_remove(uq);
1321         }
1322         umtxq_unlock(&uq->uq_key);
1323         umtx_key_release(&uq->uq_key);
1324         if (error == ERESTART)
1325                 error = EINTR;
1326         return (error);
1327 }
1328
1329 /*
1330  * Wake up threads sleeping on the specified address.
1331  */
1332 int
1333 kern_umtx_wake(struct thread *td, void *uaddr, int n_wake, int is_private)
1334 {
1335         struct umtx_key key;
1336         int ret;
1337
1338         if ((ret = umtx_key_get(uaddr, TYPE_SIMPLE_WAIT,
1339             is_private ? THREAD_SHARE : AUTO_SHARE, &key)) != 0)
1340                 return (ret);
1341         umtxq_lock(&key);
1342         umtxq_signal(&key, n_wake);
1343         umtxq_unlock(&key);
1344         umtx_key_release(&key);
1345         return (0);
1346 }
1347
1348 /*
1349  * Lock PTHREAD_PRIO_NONE protocol POSIX mutex.
1350  */
1351 static int
1352 do_lock_normal(struct thread *td, struct umutex *m, uint32_t flags,
1353     struct _umtx_time *timeout, int mode)
1354 {
1355         struct abs_timeout timo;
1356         struct umtx_q *uq;
1357         uint32_t owner, old, id;
1358         int error, rv;
1359
1360         id = td->td_tid;
1361         uq = td->td_umtxq;
1362         error = 0;
1363         if (timeout != NULL)
1364                 abs_timeout_init2(&timo, timeout);
1365
1366         /*
1367          * Care must be exercised when dealing with umtx structure. It
1368          * can fault on any access.
1369          */
1370         for (;;) {
1371                 rv = fueword32(&m->m_owner, &owner);
1372                 if (rv == -1)
1373                         return (EFAULT);
1374                 if (mode == _UMUTEX_WAIT) {
1375                         if (owner == UMUTEX_UNOWNED ||
1376                             owner == UMUTEX_CONTESTED ||
1377                             owner == UMUTEX_RB_OWNERDEAD ||
1378                             owner == UMUTEX_RB_NOTRECOV)
1379                                 return (0);
1380                 } else {
1381                         /*
1382                          * Robust mutex terminated.  Kernel duty is to
1383                          * return EOWNERDEAD to the userspace.  The
1384                          * umutex.m_flags UMUTEX_NONCONSISTENT is set
1385                          * by the common userspace code.
1386                          */
1387                         if (owner == UMUTEX_RB_OWNERDEAD) {
1388                                 rv = casueword32(&m->m_owner,
1389                                     UMUTEX_RB_OWNERDEAD, &owner,
1390                                     id | UMUTEX_CONTESTED);
1391                                 if (rv == -1)
1392                                         return (EFAULT);
1393                                 if (rv == 0) {
1394                                         MPASS(owner == UMUTEX_RB_OWNERDEAD);
1395                                         return (EOWNERDEAD); /* success */
1396                                 }
1397                                 MPASS(rv == 1);
1398                                 rv = thread_check_susp(td, false);
1399                                 if (rv != 0)
1400                                         return (rv);
1401                                 continue;
1402                         }
1403                         if (owner == UMUTEX_RB_NOTRECOV)
1404                                 return (ENOTRECOVERABLE);
1405
1406                         /*
1407                          * Try the uncontested case.  This should be
1408                          * done in userland.
1409                          */
1410                         rv = casueword32(&m->m_owner, UMUTEX_UNOWNED,
1411                             &owner, id);
1412                         /* The address was invalid. */
1413                         if (rv == -1)
1414                                 return (EFAULT);
1415
1416                         /* The acquire succeeded. */
1417                         if (rv == 0) {
1418                                 MPASS(owner == UMUTEX_UNOWNED);
1419                                 return (0);
1420                         }
1421
1422                         /*
1423                          * If no one owns it but it is contested try
1424                          * to acquire it.
1425                          */
1426                         MPASS(rv == 1);
1427                         if (owner == UMUTEX_CONTESTED) {
1428                                 rv = casueword32(&m->m_owner,
1429                                     UMUTEX_CONTESTED, &owner,
1430                                     id | UMUTEX_CONTESTED);
1431                                 /* The address was invalid. */
1432                                 if (rv == -1)
1433                                         return (EFAULT);
1434                                 if (rv == 0) {
1435                                         MPASS(owner == UMUTEX_CONTESTED);
1436                                         return (0);
1437                                 }
1438                                 if (rv == 1) {
1439                                         rv = thread_check_susp(td, false);
1440                                         if (rv != 0)
1441                                                 return (rv);
1442                                 }
1443
1444                                 /*
1445                                  * If this failed the lock has
1446                                  * changed, restart.
1447                                  */
1448                                 continue;
1449                         }
1450
1451                         /* rv == 1 but not contested, likely store failure */
1452                         rv = thread_check_susp(td, false);
1453                         if (rv != 0)
1454                                 return (rv);
1455                 }
1456
1457                 if (mode == _UMUTEX_TRY)
1458                         return (EBUSY);
1459
1460                 /*
1461                  * If we caught a signal, we have retried and now
1462                  * exit immediately.
1463                  */
1464                 if (error != 0)
1465                         return (error);
1466
1467                 if ((error = umtx_key_get(m, TYPE_NORMAL_UMUTEX,
1468                     GET_SHARE(flags), &uq->uq_key)) != 0)
1469                         return (error);
1470
1471                 umtxq_lock(&uq->uq_key);
1472                 umtxq_busy(&uq->uq_key);
1473                 umtxq_insert(uq);
1474                 umtxq_unlock(&uq->uq_key);
1475
1476                 /*
1477                  * Set the contested bit so that a release in user space
1478                  * knows to use the system call for unlock.  If this fails
1479                  * either some one else has acquired the lock or it has been
1480                  * released.
1481                  */
1482                 rv = casueword32(&m->m_owner, owner, &old,
1483                     owner | UMUTEX_CONTESTED);
1484
1485                 /* The address was invalid or casueword failed to store. */
1486                 if (rv == -1 || rv == 1) {
1487                         umtxq_lock(&uq->uq_key);
1488                         umtxq_remove(uq);
1489                         umtxq_unbusy(&uq->uq_key);
1490                         umtxq_unlock(&uq->uq_key);
1491                         umtx_key_release(&uq->uq_key);
1492                         if (rv == -1)
1493                                 return (EFAULT);
1494                         if (rv == 1) {
1495                                 rv = thread_check_susp(td, false);
1496                                 if (rv != 0)
1497                                         return (rv);
1498                         }
1499                         continue;
1500                 }
1501
1502                 /*
1503                  * We set the contested bit, sleep. Otherwise the lock changed
1504                  * and we need to retry or we lost a race to the thread
1505                  * unlocking the umtx.
1506                  */
1507                 umtxq_lock(&uq->uq_key);
1508                 umtxq_unbusy(&uq->uq_key);
1509                 MPASS(old == owner);
1510                 error = umtxq_sleep(uq, "umtxn", timeout == NULL ?
1511                     NULL : &timo);
1512                 umtxq_remove(uq);
1513                 umtxq_unlock(&uq->uq_key);
1514                 umtx_key_release(&uq->uq_key);
1515
1516                 if (error == 0)
1517                         error = thread_check_susp(td, false);
1518         }
1519
1520         return (0);
1521 }
1522
1523 /*
1524  * Unlock PTHREAD_PRIO_NONE protocol POSIX mutex.
1525  */
1526 static int
1527 do_unlock_normal(struct thread *td, struct umutex *m, uint32_t flags, bool rb)
1528 {
1529         struct umtx_key key;
1530         uint32_t owner, old, id, newlock;
1531         int error, count;
1532
1533         id = td->td_tid;
1534
1535 again:
1536         /*
1537          * Make sure we own this mtx.
1538          */
1539         error = fueword32(&m->m_owner, &owner);
1540         if (error == -1)
1541                 return (EFAULT);
1542
1543         if ((owner & ~UMUTEX_CONTESTED) != id)
1544                 return (EPERM);
1545
1546         newlock = umtx_unlock_val(flags, rb);
1547         if ((owner & UMUTEX_CONTESTED) == 0) {
1548                 error = casueword32(&m->m_owner, owner, &old, newlock);
1549                 if (error == -1)
1550                         return (EFAULT);
1551                 if (error == 1) {
1552                         error = thread_check_susp(td, false);
1553                         if (error != 0)
1554                                 return (error);
1555                         goto again;
1556                 }
1557                 MPASS(old == owner);
1558                 return (0);
1559         }
1560
1561         /* We should only ever be in here for contested locks */
1562         if ((error = umtx_key_get(m, TYPE_NORMAL_UMUTEX, GET_SHARE(flags),
1563             &key)) != 0)
1564                 return (error);
1565
1566         umtxq_lock(&key);
1567         umtxq_busy(&key);
1568         count = umtxq_count(&key);
1569         umtxq_unlock(&key);
1570
1571         /*
1572          * When unlocking the umtx, it must be marked as unowned if
1573          * there is zero or one thread only waiting for it.
1574          * Otherwise, it must be marked as contested.
1575          */
1576         if (count > 1)
1577                 newlock |= UMUTEX_CONTESTED;
1578         error = casueword32(&m->m_owner, owner, &old, newlock);
1579         umtxq_lock(&key);
1580         umtxq_signal(&key, 1);
1581         umtxq_unbusy(&key);
1582         umtxq_unlock(&key);
1583         umtx_key_release(&key);
1584         if (error == -1)
1585                 return (EFAULT);
1586         if (error == 1) {
1587                 if (old != owner)
1588                         return (EINVAL);
1589                 error = thread_check_susp(td, false);
1590                 if (error != 0)
1591                         return (error);
1592                 goto again;
1593         }
1594         return (0);
1595 }
1596
1597 /*
1598  * Check if the mutex is available and wake up a waiter,
1599  * only for simple mutex.
1600  */
1601 static int
1602 do_wake_umutex(struct thread *td, struct umutex *m)
1603 {
1604         struct umtx_key key;
1605         uint32_t owner;
1606         uint32_t flags;
1607         int error;
1608         int count;
1609
1610 again:
1611         error = fueword32(&m->m_owner, &owner);
1612         if (error == -1)
1613                 return (EFAULT);
1614
1615         if ((owner & ~UMUTEX_CONTESTED) != 0 && owner != UMUTEX_RB_OWNERDEAD &&
1616             owner != UMUTEX_RB_NOTRECOV)
1617                 return (0);
1618
1619         error = fueword32(&m->m_flags, &flags);
1620         if (error == -1)
1621                 return (EFAULT);
1622
1623         /* We should only ever be in here for contested locks */
1624         if ((error = umtx_key_get(m, TYPE_NORMAL_UMUTEX, GET_SHARE(flags),
1625             &key)) != 0)
1626                 return (error);
1627
1628         umtxq_lock(&key);
1629         umtxq_busy(&key);
1630         count = umtxq_count(&key);
1631         umtxq_unlock(&key);
1632
1633         if (count <= 1 && owner != UMUTEX_RB_OWNERDEAD &&
1634             owner != UMUTEX_RB_NOTRECOV) {
1635                 error = casueword32(&m->m_owner, UMUTEX_CONTESTED, &owner,
1636                     UMUTEX_UNOWNED);
1637                 if (error == -1) {
1638                         error = EFAULT;
1639                 } else if (error == 1) {
1640                         umtxq_lock(&key);
1641                         umtxq_unbusy(&key);
1642                         umtxq_unlock(&key);
1643                         umtx_key_release(&key);
1644                         error = thread_check_susp(td, false);
1645                         if (error != 0)
1646                                 return (error);
1647                         goto again;
1648                 }
1649         }
1650
1651         umtxq_lock(&key);
1652         if (error == 0 && count != 0) {
1653                 MPASS((owner & ~UMUTEX_CONTESTED) == 0 ||
1654                     owner == UMUTEX_RB_OWNERDEAD ||
1655                     owner == UMUTEX_RB_NOTRECOV);
1656                 umtxq_signal(&key, 1);
1657         }
1658         umtxq_unbusy(&key);
1659         umtxq_unlock(&key);
1660         umtx_key_release(&key);
1661         return (error);
1662 }
1663
1664 /*
1665  * Check if the mutex has waiters and tries to fix contention bit.
1666  */
1667 static int
1668 do_wake2_umutex(struct thread *td, struct umutex *m, uint32_t flags)
1669 {
1670         struct umtx_key key;
1671         uint32_t owner, old;
1672         int type;
1673         int error;
1674         int count;
1675
1676         switch (flags & (UMUTEX_PRIO_INHERIT | UMUTEX_PRIO_PROTECT |
1677             UMUTEX_ROBUST)) {
1678         case 0:
1679         case UMUTEX_ROBUST:
1680                 type = TYPE_NORMAL_UMUTEX;
1681                 break;
1682         case UMUTEX_PRIO_INHERIT:
1683                 type = TYPE_PI_UMUTEX;
1684                 break;
1685         case (UMUTEX_PRIO_INHERIT | UMUTEX_ROBUST):
1686                 type = TYPE_PI_ROBUST_UMUTEX;
1687                 break;
1688         case UMUTEX_PRIO_PROTECT:
1689                 type = TYPE_PP_UMUTEX;
1690                 break;
1691         case (UMUTEX_PRIO_PROTECT | UMUTEX_ROBUST):
1692                 type = TYPE_PP_ROBUST_UMUTEX;
1693                 break;
1694         default:
1695                 return (EINVAL);
1696         }
1697         if ((error = umtx_key_get(m, type, GET_SHARE(flags), &key)) != 0)
1698                 return (error);
1699
1700         owner = 0;
1701         umtxq_lock(&key);
1702         umtxq_busy(&key);
1703         count = umtxq_count(&key);
1704         umtxq_unlock(&key);
1705
1706         error = fueword32(&m->m_owner, &owner);
1707         if (error == -1)
1708                 error = EFAULT;
1709
1710         /*
1711          * Only repair contention bit if there is a waiter, this means
1712          * the mutex is still being referenced by userland code,
1713          * otherwise don't update any memory.
1714          */
1715         while (error == 0 && (owner & UMUTEX_CONTESTED) == 0 &&
1716             (count > 1 || (count == 1 && (owner & ~UMUTEX_CONTESTED) != 0))) {
1717                 error = casueword32(&m->m_owner, owner, &old,
1718                     owner | UMUTEX_CONTESTED);
1719                 if (error == -1) {
1720                         error = EFAULT;
1721                         break;
1722                 }
1723                 if (error == 0) {
1724                         MPASS(old == owner);
1725                         break;
1726                 }
1727                 owner = old;
1728                 error = thread_check_susp(td, false);
1729         }
1730
1731         umtxq_lock(&key);
1732         if (error == EFAULT) {
1733                 umtxq_signal(&key, INT_MAX);
1734         } else if (count != 0 && ((owner & ~UMUTEX_CONTESTED) == 0 ||
1735             owner == UMUTEX_RB_OWNERDEAD || owner == UMUTEX_RB_NOTRECOV))
1736                 umtxq_signal(&key, 1);
1737         umtxq_unbusy(&key);
1738         umtxq_unlock(&key);
1739         umtx_key_release(&key);
1740         return (error);
1741 }
1742
1743 static inline struct umtx_pi *
1744 umtx_pi_alloc(int flags)
1745 {
1746         struct umtx_pi *pi;
1747
1748         pi = uma_zalloc(umtx_pi_zone, M_ZERO | flags);
1749         TAILQ_INIT(&pi->pi_blocked);
1750         atomic_add_int(&umtx_pi_allocated, 1);
1751         return (pi);
1752 }
1753
1754 static inline void
1755 umtx_pi_free(struct umtx_pi *pi)
1756 {
1757         uma_zfree(umtx_pi_zone, pi);
1758         atomic_add_int(&umtx_pi_allocated, -1);
1759 }
1760
1761 /*
1762  * Adjust the thread's position on a pi_state after its priority has been
1763  * changed.
1764  */
1765 static int
1766 umtx_pi_adjust_thread(struct umtx_pi *pi, struct thread *td)
1767 {
1768         struct umtx_q *uq, *uq1, *uq2;
1769         struct thread *td1;
1770
1771         mtx_assert(&umtx_lock, MA_OWNED);
1772         if (pi == NULL)
1773                 return (0);
1774
1775         uq = td->td_umtxq;
1776
1777         /*
1778          * Check if the thread needs to be moved on the blocked chain.
1779          * It needs to be moved if either its priority is lower than
1780          * the previous thread or higher than the next thread.
1781          */
1782         uq1 = TAILQ_PREV(uq, umtxq_head, uq_lockq);
1783         uq2 = TAILQ_NEXT(uq, uq_lockq);
1784         if ((uq1 != NULL && UPRI(td) < UPRI(uq1->uq_thread)) ||
1785             (uq2 != NULL && UPRI(td) > UPRI(uq2->uq_thread))) {
1786                 /*
1787                  * Remove thread from blocked chain and determine where
1788                  * it should be moved to.
1789                  */
1790                 TAILQ_REMOVE(&pi->pi_blocked, uq, uq_lockq);
1791                 TAILQ_FOREACH(uq1, &pi->pi_blocked, uq_lockq) {
1792                         td1 = uq1->uq_thread;
1793                         MPASS(td1->td_proc->p_magic == P_MAGIC);
1794                         if (UPRI(td1) > UPRI(td))
1795                                 break;
1796                 }
1797
1798                 if (uq1 == NULL)
1799                         TAILQ_INSERT_TAIL(&pi->pi_blocked, uq, uq_lockq);
1800                 else
1801                         TAILQ_INSERT_BEFORE(uq1, uq, uq_lockq);
1802         }
1803         return (1);
1804 }
1805
1806 static struct umtx_pi *
1807 umtx_pi_next(struct umtx_pi *pi)
1808 {
1809         struct umtx_q *uq_owner;
1810
1811         if (pi->pi_owner == NULL)
1812                 return (NULL);
1813         uq_owner = pi->pi_owner->td_umtxq;
1814         if (uq_owner == NULL)
1815                 return (NULL);
1816         return (uq_owner->uq_pi_blocked);
1817 }
1818
1819 /*
1820  * Floyd's Cycle-Finding Algorithm.
1821  */
1822 static bool
1823 umtx_pi_check_loop(struct umtx_pi *pi)
1824 {
1825         struct umtx_pi *pi1;    /* fast iterator */
1826
1827         mtx_assert(&umtx_lock, MA_OWNED);
1828         if (pi == NULL)
1829                 return (false);
1830         pi1 = pi;
1831         for (;;) {
1832                 pi = umtx_pi_next(pi);
1833                 if (pi == NULL)
1834                         break;
1835                 pi1 = umtx_pi_next(pi1);
1836                 if (pi1 == NULL)
1837                         break;
1838                 pi1 = umtx_pi_next(pi1);
1839                 if (pi1 == NULL)
1840                         break;
1841                 if (pi == pi1)
1842                         return (true);
1843         }
1844         return (false);
1845 }
1846
1847 /*
1848  * Propagate priority when a thread is blocked on POSIX
1849  * PI mutex.
1850  */
1851 static void
1852 umtx_propagate_priority(struct thread *td)
1853 {
1854         struct umtx_q *uq;
1855         struct umtx_pi *pi;
1856         int pri;
1857
1858         mtx_assert(&umtx_lock, MA_OWNED);
1859         pri = UPRI(td);
1860         uq = td->td_umtxq;
1861         pi = uq->uq_pi_blocked;
1862         if (pi == NULL)
1863                 return;
1864         if (umtx_pi_check_loop(pi))
1865                 return;
1866
1867         for (;;) {
1868                 td = pi->pi_owner;
1869                 if (td == NULL || td == curthread)
1870                         return;
1871
1872                 MPASS(td->td_proc != NULL);
1873                 MPASS(td->td_proc->p_magic == P_MAGIC);
1874
1875                 thread_lock(td);
1876                 if (td->td_lend_user_pri > pri)
1877                         sched_lend_user_prio(td, pri);
1878                 else {
1879                         thread_unlock(td);
1880                         break;
1881                 }
1882                 thread_unlock(td);
1883
1884                 /*
1885                  * Pick up the lock that td is blocked on.
1886                  */
1887                 uq = td->td_umtxq;
1888                 pi = uq->uq_pi_blocked;
1889                 if (pi == NULL)
1890                         break;
1891                 /* Resort td on the list if needed. */
1892                 umtx_pi_adjust_thread(pi, td);
1893         }
1894 }
1895
1896 /*
1897  * Unpropagate priority for a PI mutex when a thread blocked on
1898  * it is interrupted by signal or resumed by others.
1899  */
1900 static void
1901 umtx_repropagate_priority(struct umtx_pi *pi)
1902 {
1903         struct umtx_q *uq, *uq_owner;
1904         struct umtx_pi *pi2;
1905         int pri;
1906
1907         mtx_assert(&umtx_lock, MA_OWNED);
1908
1909         if (umtx_pi_check_loop(pi))
1910                 return;
1911         while (pi != NULL && pi->pi_owner != NULL) {
1912                 pri = PRI_MAX;
1913                 uq_owner = pi->pi_owner->td_umtxq;
1914
1915                 TAILQ_FOREACH(pi2, &uq_owner->uq_pi_contested, pi_link) {
1916                         uq = TAILQ_FIRST(&pi2->pi_blocked);
1917                         if (uq != NULL) {
1918                                 if (pri > UPRI(uq->uq_thread))
1919                                         pri = UPRI(uq->uq_thread);
1920                         }
1921                 }
1922
1923                 if (pri > uq_owner->uq_inherited_pri)
1924                         pri = uq_owner->uq_inherited_pri;
1925                 thread_lock(pi->pi_owner);
1926                 sched_lend_user_prio(pi->pi_owner, pri);
1927                 thread_unlock(pi->pi_owner);
1928                 if ((pi = uq_owner->uq_pi_blocked) != NULL)
1929                         umtx_pi_adjust_thread(pi, uq_owner->uq_thread);
1930         }
1931 }
1932
1933 /*
1934  * Insert a PI mutex into owned list.
1935  */
1936 static void
1937 umtx_pi_setowner(struct umtx_pi *pi, struct thread *owner)
1938 {
1939         struct umtx_q *uq_owner;
1940
1941         uq_owner = owner->td_umtxq;
1942         mtx_assert(&umtx_lock, MA_OWNED);
1943         MPASS(pi->pi_owner == NULL);
1944         pi->pi_owner = owner;
1945         TAILQ_INSERT_TAIL(&uq_owner->uq_pi_contested, pi, pi_link);
1946 }
1947
1948 /*
1949  * Disown a PI mutex, and remove it from the owned list.
1950  */
1951 static void
1952 umtx_pi_disown(struct umtx_pi *pi)
1953 {
1954
1955         mtx_assert(&umtx_lock, MA_OWNED);
1956         TAILQ_REMOVE(&pi->pi_owner->td_umtxq->uq_pi_contested, pi, pi_link);
1957         pi->pi_owner = NULL;
1958 }
1959
1960 /*
1961  * Claim ownership of a PI mutex.
1962  */
1963 static int
1964 umtx_pi_claim(struct umtx_pi *pi, struct thread *owner)
1965 {
1966         struct umtx_q *uq;
1967         int pri;
1968
1969         mtx_lock(&umtx_lock);
1970         if (pi->pi_owner == owner) {
1971                 mtx_unlock(&umtx_lock);
1972                 return (0);
1973         }
1974
1975         if (pi->pi_owner != NULL) {
1976                 /*
1977                  * userland may have already messed the mutex, sigh.
1978                  */
1979                 mtx_unlock(&umtx_lock);
1980                 return (EPERM);
1981         }
1982         umtx_pi_setowner(pi, owner);
1983         uq = TAILQ_FIRST(&pi->pi_blocked);
1984         if (uq != NULL) {
1985                 pri = UPRI(uq->uq_thread);
1986                 thread_lock(owner);
1987                 if (pri < UPRI(owner))
1988                         sched_lend_user_prio(owner, pri);
1989                 thread_unlock(owner);
1990         }
1991         mtx_unlock(&umtx_lock);
1992         return (0);
1993 }
1994
1995 /*
1996  * Adjust a thread's order position in its blocked PI mutex,
1997  * this may result new priority propagating process.
1998  */
1999 void
2000 umtx_pi_adjust(struct thread *td, u_char oldpri)
2001 {
2002         struct umtx_q *uq;
2003         struct umtx_pi *pi;
2004
2005         uq = td->td_umtxq;
2006         mtx_lock(&umtx_lock);
2007         /*
2008          * Pick up the lock that td is blocked on.
2009          */
2010         pi = uq->uq_pi_blocked;
2011         if (pi != NULL) {
2012                 umtx_pi_adjust_thread(pi, td);
2013                 umtx_repropagate_priority(pi);
2014         }
2015         mtx_unlock(&umtx_lock);
2016 }
2017
2018 /*
2019  * Sleep on a PI mutex.
2020  */
2021 static int
2022 umtxq_sleep_pi(struct umtx_q *uq, struct umtx_pi *pi, uint32_t owner,
2023     const char *wmesg, struct abs_timeout *timo, bool shared)
2024 {
2025         struct thread *td, *td1;
2026         struct umtx_q *uq1;
2027         int error, pri;
2028 #ifdef INVARIANTS
2029         struct umtxq_chain *uc;
2030
2031         uc = umtxq_getchain(&pi->pi_key);
2032 #endif
2033         error = 0;
2034         td = uq->uq_thread;
2035         KASSERT(td == curthread, ("inconsistent uq_thread"));
2036         UMTXQ_LOCKED_ASSERT(umtxq_getchain(&uq->uq_key));
2037         KASSERT(uc->uc_busy != 0, ("umtx chain is not busy"));
2038         umtxq_insert(uq);
2039         mtx_lock(&umtx_lock);
2040         if (pi->pi_owner == NULL) {
2041                 mtx_unlock(&umtx_lock);
2042                 td1 = tdfind(owner, shared ? -1 : td->td_proc->p_pid);
2043                 mtx_lock(&umtx_lock);
2044                 if (td1 != NULL) {
2045                         if (pi->pi_owner == NULL)
2046                                 umtx_pi_setowner(pi, td1);
2047                         PROC_UNLOCK(td1->td_proc);
2048                 }
2049         }
2050
2051         TAILQ_FOREACH(uq1, &pi->pi_blocked, uq_lockq) {
2052                 pri = UPRI(uq1->uq_thread);
2053                 if (pri > UPRI(td))
2054                         break;
2055         }
2056
2057         if (uq1 != NULL)
2058                 TAILQ_INSERT_BEFORE(uq1, uq, uq_lockq);
2059         else
2060                 TAILQ_INSERT_TAIL(&pi->pi_blocked, uq, uq_lockq);
2061
2062         uq->uq_pi_blocked = pi;
2063         thread_lock(td);
2064         td->td_flags |= TDF_UPIBLOCKED;
2065         thread_unlock(td);
2066         umtx_propagate_priority(td);
2067         mtx_unlock(&umtx_lock);
2068         umtxq_unbusy(&uq->uq_key);
2069
2070         error = umtxq_sleep(uq, wmesg, timo);
2071         umtxq_remove(uq);
2072
2073         mtx_lock(&umtx_lock);
2074         uq->uq_pi_blocked = NULL;
2075         thread_lock(td);
2076         td->td_flags &= ~TDF_UPIBLOCKED;
2077         thread_unlock(td);
2078         TAILQ_REMOVE(&pi->pi_blocked, uq, uq_lockq);
2079         umtx_repropagate_priority(pi);
2080         mtx_unlock(&umtx_lock);
2081         umtxq_unlock(&uq->uq_key);
2082
2083         return (error);
2084 }
2085
2086 /*
2087  * Add reference count for a PI mutex.
2088  */
2089 static void
2090 umtx_pi_ref(struct umtx_pi *pi)
2091 {
2092
2093         UMTXQ_LOCKED_ASSERT(umtxq_getchain(&pi->pi_key));
2094         pi->pi_refcount++;
2095 }
2096
2097 /*
2098  * Decrease reference count for a PI mutex, if the counter
2099  * is decreased to zero, its memory space is freed.
2100  */
2101 static void
2102 umtx_pi_unref(struct umtx_pi *pi)
2103 {
2104         struct umtxq_chain *uc;
2105
2106         uc = umtxq_getchain(&pi->pi_key);
2107         UMTXQ_LOCKED_ASSERT(uc);
2108         KASSERT(pi->pi_refcount > 0, ("invalid reference count"));
2109         if (--pi->pi_refcount == 0) {
2110                 mtx_lock(&umtx_lock);
2111                 if (pi->pi_owner != NULL)
2112                         umtx_pi_disown(pi);
2113                 KASSERT(TAILQ_EMPTY(&pi->pi_blocked),
2114                         ("blocked queue not empty"));
2115                 mtx_unlock(&umtx_lock);
2116                 TAILQ_REMOVE(&uc->uc_pi_list, pi, pi_hashlink);
2117                 umtx_pi_free(pi);
2118         }
2119 }
2120
2121 /*
2122  * Find a PI mutex in hash table.
2123  */
2124 static struct umtx_pi *
2125 umtx_pi_lookup(struct umtx_key *key)
2126 {
2127         struct umtxq_chain *uc;
2128         struct umtx_pi *pi;
2129
2130         uc = umtxq_getchain(key);
2131         UMTXQ_LOCKED_ASSERT(uc);
2132
2133         TAILQ_FOREACH(pi, &uc->uc_pi_list, pi_hashlink) {
2134                 if (umtx_key_match(&pi->pi_key, key)) {
2135                         return (pi);
2136                 }
2137         }
2138         return (NULL);
2139 }
2140
2141 /*
2142  * Insert a PI mutex into hash table.
2143  */
2144 static inline void
2145 umtx_pi_insert(struct umtx_pi *pi)
2146 {
2147         struct umtxq_chain *uc;
2148
2149         uc = umtxq_getchain(&pi->pi_key);
2150         UMTXQ_LOCKED_ASSERT(uc);
2151         TAILQ_INSERT_TAIL(&uc->uc_pi_list, pi, pi_hashlink);
2152 }
2153
2154 /*
2155  * Lock a PI mutex.
2156  */
2157 static int
2158 do_lock_pi(struct thread *td, struct umutex *m, uint32_t flags,
2159     struct _umtx_time *timeout, int try)
2160 {
2161         struct abs_timeout timo;
2162         struct umtx_q *uq;
2163         struct umtx_pi *pi, *new_pi;
2164         uint32_t id, old_owner, owner, old;
2165         int error, rv;
2166
2167         id = td->td_tid;
2168         uq = td->td_umtxq;
2169
2170         if ((error = umtx_key_get(m, (flags & UMUTEX_ROBUST) != 0 ?
2171             TYPE_PI_ROBUST_UMUTEX : TYPE_PI_UMUTEX, GET_SHARE(flags),
2172             &uq->uq_key)) != 0)
2173                 return (error);
2174
2175         if (timeout != NULL)
2176                 abs_timeout_init2(&timo, timeout);
2177
2178         umtxq_lock(&uq->uq_key);
2179         pi = umtx_pi_lookup(&uq->uq_key);
2180         if (pi == NULL) {
2181                 new_pi = umtx_pi_alloc(M_NOWAIT);
2182                 if (new_pi == NULL) {
2183                         umtxq_unlock(&uq->uq_key);
2184                         new_pi = umtx_pi_alloc(M_WAITOK);
2185                         umtxq_lock(&uq->uq_key);
2186                         pi = umtx_pi_lookup(&uq->uq_key);
2187                         if (pi != NULL) {
2188                                 umtx_pi_free(new_pi);
2189                                 new_pi = NULL;
2190                         }
2191                 }
2192                 if (new_pi != NULL) {
2193                         new_pi->pi_key = uq->uq_key;
2194                         umtx_pi_insert(new_pi);
2195                         pi = new_pi;
2196                 }
2197         }
2198         umtx_pi_ref(pi);
2199         umtxq_unlock(&uq->uq_key);
2200
2201         /*
2202          * Care must be exercised when dealing with umtx structure.  It
2203          * can fault on any access.
2204          */
2205         for (;;) {
2206                 /*
2207                  * Try the uncontested case.  This should be done in userland.
2208                  */
2209                 rv = casueword32(&m->m_owner, UMUTEX_UNOWNED, &owner, id);
2210                 /* The address was invalid. */
2211                 if (rv == -1) {
2212                         error = EFAULT;
2213                         break;
2214                 }
2215                 /* The acquire succeeded. */
2216                 if (rv == 0) {
2217                         MPASS(owner == UMUTEX_UNOWNED);
2218                         error = 0;
2219                         break;
2220                 }
2221
2222                 if (owner == UMUTEX_RB_NOTRECOV) {
2223                         error = ENOTRECOVERABLE;
2224                         break;
2225                 }
2226
2227                 /*
2228                  * Nobody owns it, but the acquire failed. This can happen
2229                  * with ll/sc atomics.
2230                  */
2231                 if (owner == UMUTEX_UNOWNED) {
2232                         error = thread_check_susp(td, true);
2233                         if (error != 0)
2234                                 break;
2235                         continue;
2236                 }
2237
2238                 /*
2239                  * Avoid overwriting a possible error from sleep due
2240                  * to the pending signal with suspension check result.
2241                  */
2242                 if (error == 0) {
2243                         error = thread_check_susp(td, true);
2244                         if (error != 0)
2245                                 break;
2246                 }
2247
2248                 /* If no one owns it but it is contested try to acquire it. */
2249                 if (owner == UMUTEX_CONTESTED || owner == UMUTEX_RB_OWNERDEAD) {
2250                         old_owner = owner;
2251                         rv = casueword32(&m->m_owner, owner, &owner,
2252                             id | UMUTEX_CONTESTED);
2253                         /* The address was invalid. */
2254                         if (rv == -1) {
2255                                 error = EFAULT;
2256                                 break;
2257                         }
2258                         if (rv == 1) {
2259                                 if (error == 0) {
2260                                         error = thread_check_susp(td, true);
2261                                         if (error != 0)
2262                                                 break;
2263                                 }
2264
2265                                 /*
2266                                  * If this failed the lock could
2267                                  * changed, restart.
2268                                  */
2269                                 continue;
2270                         }
2271
2272                         MPASS(rv == 0);
2273                         MPASS(owner == old_owner);
2274                         umtxq_lock(&uq->uq_key);
2275                         umtxq_busy(&uq->uq_key);
2276                         error = umtx_pi_claim(pi, td);
2277                         umtxq_unbusy(&uq->uq_key);
2278                         umtxq_unlock(&uq->uq_key);
2279                         if (error != 0) {
2280                                 /*
2281                                  * Since we're going to return an
2282                                  * error, restore the m_owner to its
2283                                  * previous, unowned state to avoid
2284                                  * compounding the problem.
2285                                  */
2286                                 (void)casuword32(&m->m_owner,
2287                                     id | UMUTEX_CONTESTED, old_owner);
2288                         }
2289                         if (error == 0 && old_owner == UMUTEX_RB_OWNERDEAD)
2290                                 error = EOWNERDEAD;
2291                         break;
2292                 }
2293
2294                 if ((owner & ~UMUTEX_CONTESTED) == id) {
2295                         error = EDEADLK;
2296                         break;
2297                 }
2298
2299                 if (try != 0) {
2300                         error = EBUSY;
2301                         break;
2302                 }
2303
2304                 /*
2305                  * If we caught a signal, we have retried and now
2306                  * exit immediately.
2307                  */
2308                 if (error != 0)
2309                         break;
2310
2311                 umtxq_lock(&uq->uq_key);
2312                 umtxq_busy(&uq->uq_key);
2313                 umtxq_unlock(&uq->uq_key);
2314
2315                 /*
2316                  * Set the contested bit so that a release in user space
2317                  * knows to use the system call for unlock.  If this fails
2318                  * either some one else has acquired the lock or it has been
2319                  * released.
2320                  */
2321                 rv = casueword32(&m->m_owner, owner, &old, owner |
2322                     UMUTEX_CONTESTED);
2323
2324                 /* The address was invalid. */
2325                 if (rv == -1) {
2326                         umtxq_unbusy_unlocked(&uq->uq_key);
2327                         error = EFAULT;
2328                         break;
2329                 }
2330                 if (rv == 1) {
2331                         umtxq_unbusy_unlocked(&uq->uq_key);
2332                         error = thread_check_susp(td, true);
2333                         if (error != 0)
2334                                 break;
2335
2336                         /*
2337                          * The lock changed and we need to retry or we
2338                          * lost a race to the thread unlocking the
2339                          * umtx.  Note that the UMUTEX_RB_OWNERDEAD
2340                          * value for owner is impossible there.
2341                          */
2342                         continue;
2343                 }
2344
2345                 umtxq_lock(&uq->uq_key);
2346
2347                 /* We set the contested bit, sleep. */
2348                 MPASS(old == owner);
2349                 error = umtxq_sleep_pi(uq, pi, owner & ~UMUTEX_CONTESTED,
2350                     "umtxpi", timeout == NULL ? NULL : &timo,
2351                     (flags & USYNC_PROCESS_SHARED) != 0);
2352                 if (error != 0)
2353                         continue;
2354
2355                 error = thread_check_susp(td, false);
2356                 if (error != 0)
2357                         break;
2358         }
2359
2360         umtxq_lock(&uq->uq_key);
2361         umtx_pi_unref(pi);
2362         umtxq_unlock(&uq->uq_key);
2363
2364         umtx_key_release(&uq->uq_key);
2365         return (error);
2366 }
2367
2368 /*
2369  * Unlock a PI mutex.
2370  */
2371 static int
2372 do_unlock_pi(struct thread *td, struct umutex *m, uint32_t flags, bool rb)
2373 {
2374         struct umtx_key key;
2375         struct umtx_q *uq_first, *uq_first2, *uq_me;
2376         struct umtx_pi *pi, *pi2;
2377         uint32_t id, new_owner, old, owner;
2378         int count, error, pri;
2379
2380         id = td->td_tid;
2381
2382 usrloop:
2383         /*
2384          * Make sure we own this mtx.
2385          */
2386         error = fueword32(&m->m_owner, &owner);
2387         if (error == -1)
2388                 return (EFAULT);
2389
2390         if ((owner & ~UMUTEX_CONTESTED) != id)
2391                 return (EPERM);
2392
2393         new_owner = umtx_unlock_val(flags, rb);
2394
2395         /* This should be done in userland */
2396         if ((owner & UMUTEX_CONTESTED) == 0) {
2397                 error = casueword32(&m->m_owner, owner, &old, new_owner);
2398                 if (error == -1)
2399                         return (EFAULT);
2400                 if (error == 1) {
2401                         error = thread_check_susp(td, true);
2402                         if (error != 0)
2403                                 return (error);
2404                         goto usrloop;
2405                 }
2406                 if (old == owner)
2407                         return (0);
2408                 owner = old;
2409         }
2410
2411         /* We should only ever be in here for contested locks */
2412         if ((error = umtx_key_get(m, (flags & UMUTEX_ROBUST) != 0 ?
2413             TYPE_PI_ROBUST_UMUTEX : TYPE_PI_UMUTEX, GET_SHARE(flags),
2414             &key)) != 0)
2415                 return (error);
2416
2417         umtxq_lock(&key);
2418         umtxq_busy(&key);
2419         count = umtxq_count_pi(&key, &uq_first);
2420         if (uq_first != NULL) {
2421                 mtx_lock(&umtx_lock);
2422                 pi = uq_first->uq_pi_blocked;
2423                 KASSERT(pi != NULL, ("pi == NULL?"));
2424                 if (pi->pi_owner != td && !(rb && pi->pi_owner == NULL)) {
2425                         mtx_unlock(&umtx_lock);
2426                         umtxq_unbusy(&key);
2427                         umtxq_unlock(&key);
2428                         umtx_key_release(&key);
2429                         /* userland messed the mutex */
2430                         return (EPERM);
2431                 }
2432                 uq_me = td->td_umtxq;
2433                 if (pi->pi_owner == td)
2434                         umtx_pi_disown(pi);
2435                 /* get highest priority thread which is still sleeping. */
2436                 uq_first = TAILQ_FIRST(&pi->pi_blocked);
2437                 while (uq_first != NULL &&
2438                     (uq_first->uq_flags & UQF_UMTXQ) == 0) {
2439                         uq_first = TAILQ_NEXT(uq_first, uq_lockq);
2440                 }
2441                 pri = PRI_MAX;
2442                 TAILQ_FOREACH(pi2, &uq_me->uq_pi_contested, pi_link) {
2443                         uq_first2 = TAILQ_FIRST(&pi2->pi_blocked);
2444                         if (uq_first2 != NULL) {
2445                                 if (pri > UPRI(uq_first2->uq_thread))
2446                                         pri = UPRI(uq_first2->uq_thread);
2447                         }
2448                 }
2449                 thread_lock(td);
2450                 sched_lend_user_prio(td, pri);
2451                 thread_unlock(td);
2452                 mtx_unlock(&umtx_lock);
2453                 if (uq_first)
2454                         umtxq_signal_thread(uq_first);
2455         } else {
2456                 pi = umtx_pi_lookup(&key);
2457                 /*
2458                  * A umtx_pi can exist if a signal or timeout removed the
2459                  * last waiter from the umtxq, but there is still
2460                  * a thread in do_lock_pi() holding the umtx_pi.
2461                  */
2462                 if (pi != NULL) {
2463                         /*
2464                          * The umtx_pi can be unowned, such as when a thread
2465                          * has just entered do_lock_pi(), allocated the
2466                          * umtx_pi, and unlocked the umtxq.
2467                          * If the current thread owns it, it must disown it.
2468                          */
2469                         mtx_lock(&umtx_lock);
2470                         if (pi->pi_owner == td)
2471                                 umtx_pi_disown(pi);
2472                         mtx_unlock(&umtx_lock);
2473                 }
2474         }
2475         umtxq_unlock(&key);
2476
2477         /*
2478          * When unlocking the umtx, it must be marked as unowned if
2479          * there is zero or one thread only waiting for it.
2480          * Otherwise, it must be marked as contested.
2481          */
2482
2483         if (count > 1)
2484                 new_owner |= UMUTEX_CONTESTED;
2485 again:
2486         error = casueword32(&m->m_owner, owner, &old, new_owner);
2487         if (error == 1) {
2488                 error = thread_check_susp(td, false);
2489                 if (error == 0)
2490                         goto again;
2491         }
2492         umtxq_unbusy_unlocked(&key);
2493         umtx_key_release(&key);
2494         if (error == -1)
2495                 return (EFAULT);
2496         if (error == 0 && old != owner)
2497                 return (EINVAL);
2498         return (error);
2499 }
2500
2501 /*
2502  * Lock a PP mutex.
2503  */
2504 static int
2505 do_lock_pp(struct thread *td, struct umutex *m, uint32_t flags,
2506     struct _umtx_time *timeout, int try)
2507 {
2508         struct abs_timeout timo;
2509         struct umtx_q *uq, *uq2;
2510         struct umtx_pi *pi;
2511         uint32_t ceiling;
2512         uint32_t owner, id;
2513         int error, pri, old_inherited_pri, su, rv;
2514
2515         id = td->td_tid;
2516         uq = td->td_umtxq;
2517         if ((error = umtx_key_get(m, (flags & UMUTEX_ROBUST) != 0 ?
2518             TYPE_PP_ROBUST_UMUTEX : TYPE_PP_UMUTEX, GET_SHARE(flags),
2519             &uq->uq_key)) != 0)
2520                 return (error);
2521
2522         if (timeout != NULL)
2523                 abs_timeout_init2(&timo, timeout);
2524
2525         su = (priv_check(td, PRIV_SCHED_RTPRIO) == 0);
2526         for (;;) {
2527                 old_inherited_pri = uq->uq_inherited_pri;
2528                 umtxq_lock(&uq->uq_key);
2529                 umtxq_busy(&uq->uq_key);
2530                 umtxq_unlock(&uq->uq_key);
2531
2532                 rv = fueword32(&m->m_ceilings[0], &ceiling);
2533                 if (rv == -1) {
2534                         error = EFAULT;
2535                         goto out;
2536                 }
2537                 ceiling = RTP_PRIO_MAX - ceiling;
2538                 if (ceiling > RTP_PRIO_MAX) {
2539                         error = EINVAL;
2540                         goto out;
2541                 }
2542
2543                 mtx_lock(&umtx_lock);
2544                 if (UPRI(td) < PRI_MIN_REALTIME + ceiling) {
2545                         mtx_unlock(&umtx_lock);
2546                         error = EINVAL;
2547                         goto out;
2548                 }
2549                 if (su && PRI_MIN_REALTIME + ceiling < uq->uq_inherited_pri) {
2550                         uq->uq_inherited_pri = PRI_MIN_REALTIME + ceiling;
2551                         thread_lock(td);
2552                         if (uq->uq_inherited_pri < UPRI(td))
2553                                 sched_lend_user_prio(td, uq->uq_inherited_pri);
2554                         thread_unlock(td);
2555                 }
2556                 mtx_unlock(&umtx_lock);
2557
2558                 rv = casueword32(&m->m_owner, UMUTEX_CONTESTED, &owner,
2559                     id | UMUTEX_CONTESTED);
2560                 /* The address was invalid. */
2561                 if (rv == -1) {
2562                         error = EFAULT;
2563                         break;
2564                 }
2565                 if (rv == 0) {
2566                         MPASS(owner == UMUTEX_CONTESTED);
2567                         error = 0;
2568                         break;
2569                 }
2570                 /* rv == 1 */
2571                 if (owner == UMUTEX_RB_OWNERDEAD) {
2572                         rv = casueword32(&m->m_owner, UMUTEX_RB_OWNERDEAD,
2573                             &owner, id | UMUTEX_CONTESTED);
2574                         if (rv == -1) {
2575                                 error = EFAULT;
2576                                 break;
2577                         }
2578                         if (rv == 0) {
2579                                 MPASS(owner == UMUTEX_RB_OWNERDEAD);
2580                                 error = EOWNERDEAD; /* success */
2581                                 break;
2582                         }
2583
2584                         /*
2585                          *  rv == 1, only check for suspension if we
2586                          *  did not already catched a signal.  If we
2587                          *  get an error from the check, the same
2588                          *  condition is checked by the umtxq_sleep()
2589                          *  call below, so we should obliterate the
2590                          *  error to not skip the last loop iteration.
2591                          */
2592                         if (error == 0) {
2593                                 error = thread_check_susp(td, false);
2594                                 if (error == 0) {
2595                                         if (try != 0)
2596                                                 error = EBUSY;
2597                                         else
2598                                                 continue;
2599                                 }
2600                                 error = 0;
2601                         }
2602                 } else if (owner == UMUTEX_RB_NOTRECOV) {
2603                         error = ENOTRECOVERABLE;
2604                 }
2605
2606                 if (try != 0)
2607                         error = EBUSY;
2608
2609                 /*
2610                  * If we caught a signal, we have retried and now
2611                  * exit immediately.
2612                  */
2613                 if (error != 0)
2614                         break;
2615
2616                 umtxq_lock(&uq->uq_key);
2617                 umtxq_insert(uq);
2618                 umtxq_unbusy(&uq->uq_key);
2619                 error = umtxq_sleep(uq, "umtxpp", timeout == NULL ?
2620                     NULL : &timo);
2621                 umtxq_remove(uq);
2622                 umtxq_unlock(&uq->uq_key);
2623
2624                 mtx_lock(&umtx_lock);
2625                 uq->uq_inherited_pri = old_inherited_pri;
2626                 pri = PRI_MAX;
2627                 TAILQ_FOREACH(pi, &uq->uq_pi_contested, pi_link) {
2628                         uq2 = TAILQ_FIRST(&pi->pi_blocked);
2629                         if (uq2 != NULL) {
2630                                 if (pri > UPRI(uq2->uq_thread))
2631                                         pri = UPRI(uq2->uq_thread);
2632                         }
2633                 }
2634                 if (pri > uq->uq_inherited_pri)
2635                         pri = uq->uq_inherited_pri;
2636                 thread_lock(td);
2637                 sched_lend_user_prio(td, pri);
2638                 thread_unlock(td);
2639                 mtx_unlock(&umtx_lock);
2640         }
2641
2642         if (error != 0 && error != EOWNERDEAD) {
2643                 mtx_lock(&umtx_lock);
2644                 uq->uq_inherited_pri = old_inherited_pri;
2645                 pri = PRI_MAX;
2646                 TAILQ_FOREACH(pi, &uq->uq_pi_contested, pi_link) {
2647                         uq2 = TAILQ_FIRST(&pi->pi_blocked);
2648                         if (uq2 != NULL) {
2649                                 if (pri > UPRI(uq2->uq_thread))
2650                                         pri = UPRI(uq2->uq_thread);
2651                         }
2652                 }
2653                 if (pri > uq->uq_inherited_pri)
2654                         pri = uq->uq_inherited_pri;
2655                 thread_lock(td);
2656                 sched_lend_user_prio(td, pri);
2657                 thread_unlock(td);
2658                 mtx_unlock(&umtx_lock);
2659         }
2660
2661 out:
2662         umtxq_unbusy_unlocked(&uq->uq_key);
2663         umtx_key_release(&uq->uq_key);
2664         return (error);
2665 }
2666
2667 /*
2668  * Unlock a PP mutex.
2669  */
2670 static int
2671 do_unlock_pp(struct thread *td, struct umutex *m, uint32_t flags, bool rb)
2672 {
2673         struct umtx_key key;
2674         struct umtx_q *uq, *uq2;
2675         struct umtx_pi *pi;
2676         uint32_t id, owner, rceiling;
2677         int error, pri, new_inherited_pri, su;
2678
2679         id = td->td_tid;
2680         uq = td->td_umtxq;
2681         su = (priv_check(td, PRIV_SCHED_RTPRIO) == 0);
2682
2683         /*
2684          * Make sure we own this mtx.
2685          */
2686         error = fueword32(&m->m_owner, &owner);
2687         if (error == -1)
2688                 return (EFAULT);
2689
2690         if ((owner & ~UMUTEX_CONTESTED) != id)
2691                 return (EPERM);
2692
2693         error = copyin(&m->m_ceilings[1], &rceiling, sizeof(uint32_t));
2694         if (error != 0)
2695                 return (error);
2696
2697         if (rceiling == -1)
2698                 new_inherited_pri = PRI_MAX;
2699         else {
2700                 rceiling = RTP_PRIO_MAX - rceiling;
2701                 if (rceiling > RTP_PRIO_MAX)
2702                         return (EINVAL);
2703                 new_inherited_pri = PRI_MIN_REALTIME + rceiling;
2704         }
2705
2706         if ((error = umtx_key_get(m, (flags & UMUTEX_ROBUST) != 0 ?
2707             TYPE_PP_ROBUST_UMUTEX : TYPE_PP_UMUTEX, GET_SHARE(flags),
2708             &key)) != 0)
2709                 return (error);
2710         umtxq_lock(&key);
2711         umtxq_busy(&key);
2712         umtxq_unlock(&key);
2713         /*
2714          * For priority protected mutex, always set unlocked state
2715          * to UMUTEX_CONTESTED, so that userland always enters kernel
2716          * to lock the mutex, it is necessary because thread priority
2717          * has to be adjusted for such mutex.
2718          */
2719         error = suword32(&m->m_owner, umtx_unlock_val(flags, rb) |
2720             UMUTEX_CONTESTED);
2721
2722         umtxq_lock(&key);
2723         if (error == 0)
2724                 umtxq_signal(&key, 1);
2725         umtxq_unbusy(&key);
2726         umtxq_unlock(&key);
2727
2728         if (error == -1)
2729                 error = EFAULT;
2730         else {
2731                 mtx_lock(&umtx_lock);
2732                 if (su != 0)
2733                         uq->uq_inherited_pri = new_inherited_pri;
2734                 pri = PRI_MAX;
2735                 TAILQ_FOREACH(pi, &uq->uq_pi_contested, pi_link) {
2736                         uq2 = TAILQ_FIRST(&pi->pi_blocked);
2737                         if (uq2 != NULL) {
2738                                 if (pri > UPRI(uq2->uq_thread))
2739                                         pri = UPRI(uq2->uq_thread);
2740                         }
2741                 }
2742                 if (pri > uq->uq_inherited_pri)
2743                         pri = uq->uq_inherited_pri;
2744                 thread_lock(td);
2745                 sched_lend_user_prio(td, pri);
2746                 thread_unlock(td);
2747                 mtx_unlock(&umtx_lock);
2748         }
2749         umtx_key_release(&key);
2750         return (error);
2751 }
2752
2753 static int
2754 do_set_ceiling(struct thread *td, struct umutex *m, uint32_t ceiling,
2755     uint32_t *old_ceiling)
2756 {
2757         struct umtx_q *uq;
2758         uint32_t flags, id, owner, save_ceiling;
2759         int error, rv, rv1;
2760
2761         error = fueword32(&m->m_flags, &flags);
2762         if (error == -1)
2763                 return (EFAULT);
2764         if ((flags & UMUTEX_PRIO_PROTECT) == 0)
2765                 return (EINVAL);
2766         if (ceiling > RTP_PRIO_MAX)
2767                 return (EINVAL);
2768         id = td->td_tid;
2769         uq = td->td_umtxq;
2770         if ((error = umtx_key_get(m, (flags & UMUTEX_ROBUST) != 0 ?
2771             TYPE_PP_ROBUST_UMUTEX : TYPE_PP_UMUTEX, GET_SHARE(flags),
2772             &uq->uq_key)) != 0)
2773                 return (error);
2774         for (;;) {
2775                 umtxq_lock(&uq->uq_key);
2776                 umtxq_busy(&uq->uq_key);
2777                 umtxq_unlock(&uq->uq_key);
2778
2779                 rv = fueword32(&m->m_ceilings[0], &save_ceiling);
2780                 if (rv == -1) {
2781                         error = EFAULT;
2782                         break;
2783                 }
2784
2785                 rv = casueword32(&m->m_owner, UMUTEX_CONTESTED, &owner,
2786                     id | UMUTEX_CONTESTED);
2787                 if (rv == -1) {
2788                         error = EFAULT;
2789                         break;
2790                 }
2791
2792                 if (rv == 0) {
2793                         MPASS(owner == UMUTEX_CONTESTED);
2794                         rv = suword32(&m->m_ceilings[0], ceiling);
2795                         rv1 = suword32(&m->m_owner, UMUTEX_CONTESTED);
2796                         error = (rv == 0 && rv1 == 0) ? 0: EFAULT;
2797                         break;
2798                 }
2799
2800                 if ((owner & ~UMUTEX_CONTESTED) == id) {
2801                         rv = suword32(&m->m_ceilings[0], ceiling);
2802                         error = rv == 0 ? 0 : EFAULT;
2803                         break;
2804                 }
2805
2806                 if (owner == UMUTEX_RB_OWNERDEAD) {
2807                         error = EOWNERDEAD;
2808                         break;
2809                 } else if (owner == UMUTEX_RB_NOTRECOV) {
2810                         error = ENOTRECOVERABLE;
2811                         break;
2812                 }
2813
2814                 /*
2815                  * If we caught a signal, we have retried and now
2816                  * exit immediately.
2817                  */
2818                 if (error != 0)
2819                         break;
2820
2821                 /*
2822                  * We set the contested bit, sleep. Otherwise the lock changed
2823                  * and we need to retry or we lost a race to the thread
2824                  * unlocking the umtx.
2825                  */
2826                 umtxq_lock(&uq->uq_key);
2827                 umtxq_insert(uq);
2828                 umtxq_unbusy(&uq->uq_key);
2829                 error = umtxq_sleep(uq, "umtxpp", NULL);
2830                 umtxq_remove(uq);
2831                 umtxq_unlock(&uq->uq_key);
2832         }
2833         umtxq_lock(&uq->uq_key);
2834         if (error == 0)
2835                 umtxq_signal(&uq->uq_key, INT_MAX);
2836         umtxq_unbusy(&uq->uq_key);
2837         umtxq_unlock(&uq->uq_key);
2838         umtx_key_release(&uq->uq_key);
2839         if (error == 0 && old_ceiling != NULL) {
2840                 rv = suword32(old_ceiling, save_ceiling);
2841                 error = rv == 0 ? 0 : EFAULT;
2842         }
2843         return (error);
2844 }
2845
2846 /*
2847  * Lock a userland POSIX mutex.
2848  */
2849 static int
2850 do_lock_umutex(struct thread *td, struct umutex *m,
2851     struct _umtx_time *timeout, int mode)
2852 {
2853         uint32_t flags;
2854         int error;
2855
2856         error = fueword32(&m->m_flags, &flags);
2857         if (error == -1)
2858                 return (EFAULT);
2859
2860         switch (flags & (UMUTEX_PRIO_INHERIT | UMUTEX_PRIO_PROTECT)) {
2861         case 0:
2862                 error = do_lock_normal(td, m, flags, timeout, mode);
2863                 break;
2864         case UMUTEX_PRIO_INHERIT:
2865                 error = do_lock_pi(td, m, flags, timeout, mode);
2866                 break;
2867         case UMUTEX_PRIO_PROTECT:
2868                 error = do_lock_pp(td, m, flags, timeout, mode);
2869                 break;
2870         default:
2871                 return (EINVAL);
2872         }
2873         if (timeout == NULL) {
2874                 if (error == EINTR && mode != _UMUTEX_WAIT)
2875                         error = ERESTART;
2876         } else {
2877                 /* Timed-locking is not restarted. */
2878                 if (error == ERESTART)
2879                         error = EINTR;
2880         }
2881         return (error);
2882 }
2883
2884 /*
2885  * Unlock a userland POSIX mutex.
2886  */
2887 static int
2888 do_unlock_umutex(struct thread *td, struct umutex *m, bool rb)
2889 {
2890         uint32_t flags;
2891         int error;
2892
2893         error = fueword32(&m->m_flags, &flags);
2894         if (error == -1)
2895                 return (EFAULT);
2896
2897         switch (flags & (UMUTEX_PRIO_INHERIT | UMUTEX_PRIO_PROTECT)) {
2898         case 0:
2899                 return (do_unlock_normal(td, m, flags, rb));
2900         case UMUTEX_PRIO_INHERIT:
2901                 return (do_unlock_pi(td, m, flags, rb));
2902         case UMUTEX_PRIO_PROTECT:
2903                 return (do_unlock_pp(td, m, flags, rb));
2904         }
2905
2906         return (EINVAL);
2907 }
2908
2909 static int
2910 do_cv_wait(struct thread *td, struct ucond *cv, struct umutex *m,
2911     struct timespec *timeout, u_long wflags)
2912 {
2913         struct abs_timeout timo;
2914         struct umtx_q *uq;
2915         uint32_t flags, clockid, hasw;
2916         int error;
2917
2918         uq = td->td_umtxq;
2919         error = fueword32(&cv->c_flags, &flags);
2920         if (error == -1)
2921                 return (EFAULT);
2922         error = umtx_key_get(cv, TYPE_CV, GET_SHARE(flags), &uq->uq_key);
2923         if (error != 0)
2924                 return (error);
2925
2926         if ((wflags & CVWAIT_CLOCKID) != 0) {
2927                 error = fueword32(&cv->c_clockid, &clockid);
2928                 if (error == -1) {
2929                         umtx_key_release(&uq->uq_key);
2930                         return (EFAULT);
2931                 }
2932                 if (clockid < CLOCK_REALTIME ||
2933                     clockid >= CLOCK_THREAD_CPUTIME_ID) {
2934                         /* hmm, only HW clock id will work. */
2935                         umtx_key_release(&uq->uq_key);
2936                         return (EINVAL);
2937                 }
2938         } else {
2939                 clockid = CLOCK_REALTIME;
2940         }
2941
2942         umtxq_lock(&uq->uq_key);
2943         umtxq_busy(&uq->uq_key);
2944         umtxq_insert(uq);
2945         umtxq_unlock(&uq->uq_key);
2946
2947         /*
2948          * Set c_has_waiters to 1 before releasing user mutex, also
2949          * don't modify cache line when unnecessary.
2950          */
2951         error = fueword32(&cv->c_has_waiters, &hasw);
2952         if (error == 0 && hasw == 0)
2953                 suword32(&cv->c_has_waiters, 1);
2954
2955         umtxq_unbusy_unlocked(&uq->uq_key);
2956
2957         error = do_unlock_umutex(td, m, false);
2958
2959         if (timeout != NULL)
2960                 abs_timeout_init(&timo, clockid, (wflags & CVWAIT_ABSTIME) != 0,
2961                     timeout);
2962
2963         umtxq_lock(&uq->uq_key);
2964         if (error == 0) {
2965                 error = umtxq_sleep(uq, "ucond", timeout == NULL ?
2966                     NULL : &timo);
2967         }
2968
2969         if ((uq->uq_flags & UQF_UMTXQ) == 0)
2970                 error = 0;
2971         else {
2972                 /*
2973                  * This must be timeout,interrupted by signal or
2974                  * surprious wakeup, clear c_has_waiter flag when
2975                  * necessary.
2976                  */
2977                 umtxq_busy(&uq->uq_key);
2978                 if ((uq->uq_flags & UQF_UMTXQ) != 0) {
2979                         int oldlen = uq->uq_cur_queue->length;
2980                         umtxq_remove(uq);
2981                         if (oldlen == 1) {
2982                                 umtxq_unlock(&uq->uq_key);
2983                                 suword32(&cv->c_has_waiters, 0);
2984                                 umtxq_lock(&uq->uq_key);
2985                         }
2986                 }
2987                 umtxq_unbusy(&uq->uq_key);
2988                 if (error == ERESTART)
2989                         error = EINTR;
2990         }
2991
2992         umtxq_unlock(&uq->uq_key);
2993         umtx_key_release(&uq->uq_key);
2994         return (error);
2995 }
2996
2997 /*
2998  * Signal a userland condition variable.
2999  */
3000 static int
3001 do_cv_signal(struct thread *td, struct ucond *cv)
3002 {
3003         struct umtx_key key;
3004         int error, cnt, nwake;
3005         uint32_t flags;
3006
3007         error = fueword32(&cv->c_flags, &flags);
3008         if (error == -1)
3009                 return (EFAULT);
3010         if ((error = umtx_key_get(cv, TYPE_CV, GET_SHARE(flags), &key)) != 0)
3011                 return (error);
3012         umtxq_lock(&key);
3013         umtxq_busy(&key);
3014         cnt = umtxq_count(&key);
3015         nwake = umtxq_signal(&key, 1);
3016         if (cnt <= nwake) {
3017                 umtxq_unlock(&key);
3018                 error = suword32(&cv->c_has_waiters, 0);
3019                 if (error == -1)
3020                         error = EFAULT;
3021                 umtxq_lock(&key);
3022         }
3023         umtxq_unbusy(&key);
3024         umtxq_unlock(&key);
3025         umtx_key_release(&key);
3026         return (error);
3027 }
3028
3029 static int
3030 do_cv_broadcast(struct thread *td, struct ucond *cv)
3031 {
3032         struct umtx_key key;
3033         int error;
3034         uint32_t flags;
3035
3036         error = fueword32(&cv->c_flags, &flags);
3037         if (error == -1)
3038                 return (EFAULT);
3039         if ((error = umtx_key_get(cv, TYPE_CV, GET_SHARE(flags), &key)) != 0)
3040                 return (error);
3041
3042         umtxq_lock(&key);
3043         umtxq_busy(&key);
3044         umtxq_signal(&key, INT_MAX);
3045         umtxq_unlock(&key);
3046
3047         error = suword32(&cv->c_has_waiters, 0);
3048         if (error == -1)
3049                 error = EFAULT;
3050
3051         umtxq_unbusy_unlocked(&key);
3052
3053         umtx_key_release(&key);
3054         return (error);
3055 }
3056
3057 static int
3058 do_rw_rdlock(struct thread *td, struct urwlock *rwlock, long fflag,
3059     struct _umtx_time *timeout)
3060 {
3061         struct abs_timeout timo;
3062         struct umtx_q *uq;
3063         uint32_t flags, wrflags;
3064         int32_t state, oldstate;
3065         int32_t blocked_readers;
3066         int error, error1, rv;
3067
3068         uq = td->td_umtxq;
3069         error = fueword32(&rwlock->rw_flags, &flags);
3070         if (error == -1)
3071                 return (EFAULT);
3072         error = umtx_key_get(rwlock, TYPE_RWLOCK, GET_SHARE(flags), &uq->uq_key);
3073         if (error != 0)
3074                 return (error);
3075
3076         if (timeout != NULL)
3077                 abs_timeout_init2(&timo, timeout);
3078
3079         wrflags = URWLOCK_WRITE_OWNER;
3080         if (!(fflag & URWLOCK_PREFER_READER) && !(flags & URWLOCK_PREFER_READER))
3081                 wrflags |= URWLOCK_WRITE_WAITERS;
3082
3083         for (;;) {
3084                 rv = fueword32(&rwlock->rw_state, &state);
3085                 if (rv == -1) {
3086                         umtx_key_release(&uq->uq_key);
3087                         return (EFAULT);
3088                 }
3089
3090                 /* try to lock it */
3091                 while (!(state & wrflags)) {
3092                         if (__predict_false(URWLOCK_READER_COUNT(state) ==
3093                             URWLOCK_MAX_READERS)) {
3094                                 umtx_key_release(&uq->uq_key);
3095                                 return (EAGAIN);
3096                         }
3097                         rv = casueword32(&rwlock->rw_state, state,
3098                             &oldstate, state + 1);
3099                         if (rv == -1) {
3100                                 umtx_key_release(&uq->uq_key);
3101                                 return (EFAULT);
3102                         }
3103                         if (rv == 0) {
3104                                 MPASS(oldstate == state);
3105                                 umtx_key_release(&uq->uq_key);
3106                                 return (0);
3107                         }
3108                         error = thread_check_susp(td, true);
3109                         if (error != 0)
3110                                 break;
3111                         state = oldstate;
3112                 }
3113
3114                 if (error)
3115                         break;
3116
3117                 /* grab monitor lock */
3118                 umtxq_lock(&uq->uq_key);
3119                 umtxq_busy(&uq->uq_key);
3120                 umtxq_unlock(&uq->uq_key);
3121
3122                 /*
3123                  * re-read the state, in case it changed between the try-lock above
3124                  * and the check below
3125                  */
3126                 rv = fueword32(&rwlock->rw_state, &state);
3127                 if (rv == -1)
3128                         error = EFAULT;
3129
3130                 /* set read contention bit */
3131                 while (error == 0 && (state & wrflags) &&
3132                     !(state & URWLOCK_READ_WAITERS)) {
3133                         rv = casueword32(&rwlock->rw_state, state,
3134                             &oldstate, state | URWLOCK_READ_WAITERS);
3135                         if (rv == -1) {
3136                                 error = EFAULT;
3137                                 break;
3138                         }
3139                         if (rv == 0) {
3140                                 MPASS(oldstate == state);
3141                                 goto sleep;
3142                         }
3143                         state = oldstate;
3144                         error = thread_check_susp(td, false);
3145                         if (error != 0)
3146                                 break;
3147                 }
3148                 if (error != 0) {
3149                         umtxq_unbusy_unlocked(&uq->uq_key);
3150                         break;
3151                 }
3152
3153                 /* state is changed while setting flags, restart */
3154                 if (!(state & wrflags)) {
3155                         umtxq_unbusy_unlocked(&uq->uq_key);
3156                         error = thread_check_susp(td, true);
3157                         if (error != 0)
3158                                 break;
3159                         continue;
3160                 }
3161
3162 sleep:
3163                 /*
3164                  * Contention bit is set, before sleeping, increase
3165                  * read waiter count.
3166                  */
3167                 rv = fueword32(&rwlock->rw_blocked_readers,
3168                     &blocked_readers);
3169                 if (rv == -1) {
3170                         umtxq_unbusy_unlocked(&uq->uq_key);
3171                         error = EFAULT;
3172                         break;
3173                 }
3174                 suword32(&rwlock->rw_blocked_readers, blocked_readers+1);
3175
3176                 while (state & wrflags) {
3177                         umtxq_lock(&uq->uq_key);
3178                         umtxq_insert(uq);
3179                         umtxq_unbusy(&uq->uq_key);
3180
3181                         error = umtxq_sleep(uq, "urdlck", timeout == NULL ?
3182                             NULL : &timo);
3183
3184                         umtxq_busy(&uq->uq_key);
3185                         umtxq_remove(uq);
3186                         umtxq_unlock(&uq->uq_key);
3187                         if (error)
3188                                 break;
3189                         rv = fueword32(&rwlock->rw_state, &state);
3190                         if (rv == -1) {
3191                                 error = EFAULT;
3192                                 break;
3193                         }
3194                 }
3195
3196                 /* decrease read waiter count, and may clear read contention bit */
3197                 rv = fueword32(&rwlock->rw_blocked_readers,
3198                     &blocked_readers);
3199                 if (rv == -1) {
3200                         umtxq_unbusy_unlocked(&uq->uq_key);
3201                         error = EFAULT;
3202                         break;
3203                 }
3204                 suword32(&rwlock->rw_blocked_readers, blocked_readers-1);
3205                 if (blocked_readers == 1) {
3206                         rv = fueword32(&rwlock->rw_state, &state);
3207                         if (rv == -1) {
3208                                 umtxq_unbusy_unlocked(&uq->uq_key);
3209                                 error = EFAULT;
3210                                 break;
3211                         }
3212                         for (;;) {
3213                                 rv = casueword32(&rwlock->rw_state, state,
3214                                     &oldstate, state & ~URWLOCK_READ_WAITERS);
3215                                 if (rv == -1) {
3216                                         error = EFAULT;
3217                                         break;
3218                                 }
3219                                 if (rv == 0) {
3220                                         MPASS(oldstate == state);
3221                                         break;
3222                                 }
3223                                 state = oldstate;
3224                                 error1 = thread_check_susp(td, false);
3225                                 if (error1 != 0) {
3226                                         if (error == 0)
3227                                                 error = error1;
3228                                         break;
3229                                 }
3230                         }
3231                 }
3232
3233                 umtxq_unbusy_unlocked(&uq->uq_key);
3234                 if (error != 0)
3235                         break;
3236         }
3237         umtx_key_release(&uq->uq_key);
3238         if (error == ERESTART)
3239                 error = EINTR;
3240         return (error);
3241 }
3242
3243 static int
3244 do_rw_wrlock(struct thread *td, struct urwlock *rwlock, struct _umtx_time *timeout)
3245 {
3246         struct abs_timeout timo;
3247         struct umtx_q *uq;
3248         uint32_t flags;
3249         int32_t state, oldstate;
3250         int32_t blocked_writers;
3251         int32_t blocked_readers;
3252         int error, error1, rv;
3253
3254         uq = td->td_umtxq;
3255         error = fueword32(&rwlock->rw_flags, &flags);
3256         if (error == -1)
3257                 return (EFAULT);
3258         error = umtx_key_get(rwlock, TYPE_RWLOCK, GET_SHARE(flags), &uq->uq_key);
3259         if (error != 0)
3260                 return (error);
3261
3262         if (timeout != NULL)
3263                 abs_timeout_init2(&timo, timeout);
3264
3265         blocked_readers = 0;
3266         for (;;) {
3267                 rv = fueword32(&rwlock->rw_state, &state);
3268                 if (rv == -1) {
3269                         umtx_key_release(&uq->uq_key);
3270                         return (EFAULT);
3271                 }
3272                 while ((state & URWLOCK_WRITE_OWNER) == 0 &&
3273                     URWLOCK_READER_COUNT(state) == 0) {
3274                         rv = casueword32(&rwlock->rw_state, state,
3275                             &oldstate, state | URWLOCK_WRITE_OWNER);
3276                         if (rv == -1) {
3277                                 umtx_key_release(&uq->uq_key);
3278                                 return (EFAULT);
3279                         }
3280                         if (rv == 0) {
3281                                 MPASS(oldstate == state);
3282                                 umtx_key_release(&uq->uq_key);
3283                                 return (0);
3284                         }
3285                         state = oldstate;
3286                         error = thread_check_susp(td, true);
3287                         if (error != 0)
3288                                 break;
3289                 }
3290
3291                 if (error) {
3292                         if ((state & (URWLOCK_WRITE_OWNER |
3293                             URWLOCK_WRITE_WAITERS)) == 0 &&
3294                             blocked_readers != 0) {
3295                                 umtxq_lock(&uq->uq_key);
3296                                 umtxq_busy(&uq->uq_key);
3297                                 umtxq_signal_queue(&uq->uq_key, INT_MAX,
3298                                     UMTX_SHARED_QUEUE);
3299                                 umtxq_unbusy(&uq->uq_key);
3300                                 umtxq_unlock(&uq->uq_key);
3301                         }
3302
3303                         break;
3304                 }
3305
3306                 /* grab monitor lock */
3307                 umtxq_lock(&uq->uq_key);
3308                 umtxq_busy(&uq->uq_key);
3309                 umtxq_unlock(&uq->uq_key);
3310
3311                 /*
3312                  * Re-read the state, in case it changed between the
3313                  * try-lock above and the check below.
3314                  */
3315                 rv = fueword32(&rwlock->rw_state, &state);
3316                 if (rv == -1)
3317                         error = EFAULT;
3318
3319                 while (error == 0 && ((state & URWLOCK_WRITE_OWNER) ||
3320                     URWLOCK_READER_COUNT(state) != 0) &&
3321                     (state & URWLOCK_WRITE_WAITERS) == 0) {
3322                         rv = casueword32(&rwlock->rw_state, state,
3323                             &oldstate, state | URWLOCK_WRITE_WAITERS);
3324                         if (rv == -1) {
3325                                 error = EFAULT;
3326                                 break;
3327                         }
3328                         if (rv == 0) {
3329                                 MPASS(oldstate == state);
3330                                 goto sleep;
3331                         }
3332                         state = oldstate;
3333                         error = thread_check_susp(td, false);
3334                         if (error != 0)
3335                                 break;
3336                 }
3337                 if (error != 0) {
3338                         umtxq_unbusy_unlocked(&uq->uq_key);
3339                         break;
3340                 }
3341
3342                 if ((state & URWLOCK_WRITE_OWNER) == 0 &&
3343                     URWLOCK_READER_COUNT(state) == 0) {
3344                         umtxq_unbusy_unlocked(&uq->uq_key);
3345                         error = thread_check_susp(td, false);
3346                         if (error != 0)
3347                                 break;
3348                         continue;
3349                 }
3350 sleep:
3351                 rv = fueword32(&rwlock->rw_blocked_writers,
3352                     &blocked_writers);
3353                 if (rv == -1) {
3354                         umtxq_unbusy_unlocked(&uq->uq_key);
3355                         error = EFAULT;
3356                         break;
3357                 }
3358                 suword32(&rwlock->rw_blocked_writers, blocked_writers + 1);
3359
3360                 while ((state & URWLOCK_WRITE_OWNER) ||
3361                     URWLOCK_READER_COUNT(state) != 0) {
3362                         umtxq_lock(&uq->uq_key);
3363                         umtxq_insert_queue(uq, UMTX_EXCLUSIVE_QUEUE);
3364                         umtxq_unbusy(&uq->uq_key);
3365
3366                         error = umtxq_sleep(uq, "uwrlck", timeout == NULL ?
3367                             NULL : &timo);
3368
3369                         umtxq_busy(&uq->uq_key);
3370                         umtxq_remove_queue(uq, UMTX_EXCLUSIVE_QUEUE);
3371                         umtxq_unlock(&uq->uq_key);
3372                         if (error)
3373                                 break;
3374                         rv = fueword32(&rwlock->rw_state, &state);
3375                         if (rv == -1) {
3376                                 error = EFAULT;
3377                                 break;
3378                         }
3379                 }
3380
3381                 rv = fueword32(&rwlock->rw_blocked_writers,
3382                     &blocked_writers);
3383                 if (rv == -1) {
3384                         umtxq_unbusy_unlocked(&uq->uq_key);
3385                         error = EFAULT;
3386                         break;
3387                 }
3388                 suword32(&rwlock->rw_blocked_writers, blocked_writers-1);
3389                 if (blocked_writers == 1) {
3390                         rv = fueword32(&rwlock->rw_state, &state);
3391                         if (rv == -1) {
3392                                 umtxq_unbusy_unlocked(&uq->uq_key);
3393                                 error = EFAULT;
3394                                 break;
3395                         }
3396                         for (;;) {
3397                                 rv = casueword32(&rwlock->rw_state, state,
3398                                     &oldstate, state & ~URWLOCK_WRITE_WAITERS);
3399                                 if (rv == -1) {
3400                                         error = EFAULT;
3401                                         break;
3402                                 }
3403                                 if (rv == 0) {
3404                                         MPASS(oldstate == state);
3405                                         break;
3406                                 }
3407                                 state = oldstate;
3408                                 error1 = thread_check_susp(td, false);
3409                                 /*
3410                                  * We are leaving the URWLOCK_WRITE_WAITERS
3411                                  * behind, but this should not harm the
3412                                  * correctness.
3413                                  */
3414                                 if (error1 != 0) {
3415                                         if (error == 0)
3416                                                 error = error1;
3417                                         break;
3418                                 }
3419                         }
3420                         rv = fueword32(&rwlock->rw_blocked_readers,
3421                             &blocked_readers);
3422                         if (rv == -1) {
3423                                 umtxq_unbusy_unlocked(&uq->uq_key);
3424                                 error = EFAULT;
3425                                 break;
3426                         }
3427                 } else
3428                         blocked_readers = 0;
3429
3430                 umtxq_unbusy_unlocked(&uq->uq_key);
3431         }
3432
3433         umtx_key_release(&uq->uq_key);
3434         if (error == ERESTART)
3435                 error = EINTR;
3436         return (error);
3437 }
3438
3439 static int
3440 do_rw_unlock(struct thread *td, struct urwlock *rwlock)
3441 {
3442         struct umtx_q *uq;
3443         uint32_t flags;
3444         int32_t state, oldstate;
3445         int error, rv, q, count;
3446
3447         uq = td->td_umtxq;
3448         error = fueword32(&rwlock->rw_flags, &flags);
3449         if (error == -1)
3450                 return (EFAULT);
3451         error = umtx_key_get(rwlock, TYPE_RWLOCK, GET_SHARE(flags), &uq->uq_key);
3452         if (error != 0)
3453                 return (error);
3454
3455         error = fueword32(&rwlock->rw_state, &state);
3456         if (error == -1) {
3457                 error = EFAULT;
3458                 goto out;
3459         }
3460         if (state & URWLOCK_WRITE_OWNER) {
3461                 for (;;) {
3462                         rv = casueword32(&rwlock->rw_state, state,
3463                             &oldstate, state & ~URWLOCK_WRITE_OWNER);
3464                         if (rv == -1) {
3465                                 error = EFAULT;
3466                                 goto out;
3467                         }
3468                         if (rv == 1) {
3469                                 state = oldstate;
3470                                 if (!(oldstate & URWLOCK_WRITE_OWNER)) {
3471                                         error = EPERM;
3472                                         goto out;
3473                                 }
3474                                 error = thread_check_susp(td, true);
3475                                 if (error != 0)
3476                                         goto out;
3477                         } else
3478                                 break;
3479                 }
3480         } else if (URWLOCK_READER_COUNT(state) != 0) {
3481                 for (;;) {
3482                         rv = casueword32(&rwlock->rw_state, state,
3483                             &oldstate, state - 1);
3484                         if (rv == -1) {
3485                                 error = EFAULT;
3486                                 goto out;
3487                         }
3488                         if (rv == 1) {
3489                                 state = oldstate;
3490                                 if (URWLOCK_READER_COUNT(oldstate) == 0) {
3491                                         error = EPERM;
3492                                         goto out;
3493                                 }
3494                                 error = thread_check_susp(td, true);
3495                                 if (error != 0)
3496                                         goto out;
3497                         } else
3498                                 break;
3499                 }
3500         } else {
3501                 error = EPERM;
3502                 goto out;
3503         }
3504
3505         count = 0;
3506
3507         if (!(flags & URWLOCK_PREFER_READER)) {
3508                 if (state & URWLOCK_WRITE_WAITERS) {
3509                         count = 1;
3510                         q = UMTX_EXCLUSIVE_QUEUE;
3511                 } else if (state & URWLOCK_READ_WAITERS) {
3512                         count = INT_MAX;
3513                         q = UMTX_SHARED_QUEUE;
3514                 }
3515         } else {
3516                 if (state & URWLOCK_READ_WAITERS) {
3517                         count = INT_MAX;
3518                         q = UMTX_SHARED_QUEUE;
3519                 } else if (state & URWLOCK_WRITE_WAITERS) {
3520                         count = 1;
3521                         q = UMTX_EXCLUSIVE_QUEUE;
3522                 }
3523         }
3524
3525         if (count) {
3526                 umtxq_lock(&uq->uq_key);
3527                 umtxq_busy(&uq->uq_key);
3528                 umtxq_signal_queue(&uq->uq_key, count, q);
3529                 umtxq_unbusy(&uq->uq_key);
3530                 umtxq_unlock(&uq->uq_key);
3531         }
3532 out:
3533         umtx_key_release(&uq->uq_key);
3534         return (error);
3535 }
3536
3537 #if defined(COMPAT_FREEBSD9) || defined(COMPAT_FREEBSD10)
3538 static int
3539 do_sem_wait(struct thread *td, struct _usem *sem, struct _umtx_time *timeout)
3540 {
3541         struct abs_timeout timo;
3542         struct umtx_q *uq;
3543         uint32_t flags, count, count1;
3544         int error, rv, rv1;
3545
3546         uq = td->td_umtxq;
3547         error = fueword32(&sem->_flags, &flags);
3548         if (error == -1)
3549                 return (EFAULT);
3550         error = umtx_key_get(sem, TYPE_SEM, GET_SHARE(flags), &uq->uq_key);
3551         if (error != 0)
3552                 return (error);
3553
3554         if (timeout != NULL)
3555                 abs_timeout_init2(&timo, timeout);
3556
3557 again:
3558         umtxq_lock(&uq->uq_key);
3559         umtxq_busy(&uq->uq_key);
3560         umtxq_insert(uq);
3561         umtxq_unlock(&uq->uq_key);
3562         rv = casueword32(&sem->_has_waiters, 0, &count1, 1);
3563         if (rv == 0)
3564                 rv1 = fueword32(&sem->_count, &count);
3565         if (rv == -1 || (rv == 0 && (rv1 == -1 || count != 0)) ||
3566             (rv == 1 && count1 == 0)) {
3567                 umtxq_lock(&uq->uq_key);
3568                 umtxq_unbusy(&uq->uq_key);
3569                 umtxq_remove(uq);
3570                 umtxq_unlock(&uq->uq_key);
3571                 if (rv == 1) {
3572                         rv = thread_check_susp(td, true);
3573                         if (rv == 0)
3574                                 goto again;
3575                         error = rv;
3576                         goto out;
3577                 }
3578                 if (rv == 0)
3579                         rv = rv1;
3580                 error = rv == -1 ? EFAULT : 0;
3581                 goto out;
3582         }
3583         umtxq_lock(&uq->uq_key);
3584         umtxq_unbusy(&uq->uq_key);
3585
3586         error = umtxq_sleep(uq, "usem", timeout == NULL ? NULL : &timo);
3587
3588         if ((uq->uq_flags & UQF_UMTXQ) == 0)
3589                 error = 0;
3590         else {
3591                 umtxq_remove(uq);
3592                 /* A relative timeout cannot be restarted. */
3593                 if (error == ERESTART && timeout != NULL &&
3594                     (timeout->_flags & UMTX_ABSTIME) == 0)
3595                         error = EINTR;
3596         }
3597         umtxq_unlock(&uq->uq_key);
3598 out:
3599         umtx_key_release(&uq->uq_key);
3600         return (error);
3601 }
3602
3603 /*
3604  * Signal a userland semaphore.
3605  */
3606 static int
3607 do_sem_wake(struct thread *td, struct _usem *sem)
3608 {
3609         struct umtx_key key;
3610         int error, cnt;
3611         uint32_t flags;
3612
3613         error = fueword32(&sem->_flags, &flags);
3614         if (error == -1)
3615                 return (EFAULT);
3616         if ((error = umtx_key_get(sem, TYPE_SEM, GET_SHARE(flags), &key)) != 0)
3617                 return (error);
3618         umtxq_lock(&key);
3619         umtxq_busy(&key);
3620         cnt = umtxq_count(&key);
3621         if (cnt > 0) {
3622                 /*
3623                  * Check if count is greater than 0, this means the memory is
3624                  * still being referenced by user code, so we can safely
3625                  * update _has_waiters flag.
3626                  */
3627                 if (cnt == 1) {
3628                         umtxq_unlock(&key);
3629                         error = suword32(&sem->_has_waiters, 0);
3630                         umtxq_lock(&key);
3631                         if (error == -1)
3632                                 error = EFAULT;
3633                 }
3634                 umtxq_signal(&key, 1);
3635         }
3636         umtxq_unbusy(&key);
3637         umtxq_unlock(&key);
3638         umtx_key_release(&key);
3639         return (error);
3640 }
3641 #endif
3642
3643 static int
3644 do_sem2_wait(struct thread *td, struct _usem2 *sem, struct _umtx_time *timeout)
3645 {
3646         struct abs_timeout timo;
3647         struct umtx_q *uq;
3648         uint32_t count, flags;
3649         int error, rv;
3650
3651         uq = td->td_umtxq;
3652         flags = fuword32(&sem->_flags);
3653         if (timeout != NULL)
3654                 abs_timeout_init2(&timo, timeout);
3655
3656 again:
3657         error = umtx_key_get(sem, TYPE_SEM, GET_SHARE(flags), &uq->uq_key);
3658         if (error != 0)
3659                 return (error);
3660         umtxq_lock(&uq->uq_key);
3661         umtxq_busy(&uq->uq_key);
3662         umtxq_insert(uq);
3663         umtxq_unlock(&uq->uq_key);
3664         rv = fueword32(&sem->_count, &count);
3665         if (rv == -1) {
3666                 umtxq_lock(&uq->uq_key);
3667                 umtxq_unbusy(&uq->uq_key);
3668                 umtxq_remove(uq);
3669                 umtxq_unlock(&uq->uq_key);
3670                 umtx_key_release(&uq->uq_key);
3671                 return (EFAULT);
3672         }
3673         for (;;) {
3674                 if (USEM_COUNT(count) != 0) {
3675                         umtxq_lock(&uq->uq_key);
3676                         umtxq_unbusy(&uq->uq_key);
3677                         umtxq_remove(uq);
3678                         umtxq_unlock(&uq->uq_key);
3679                         umtx_key_release(&uq->uq_key);
3680                         return (0);
3681                 }
3682                 if (count == USEM_HAS_WAITERS)
3683                         break;
3684                 rv = casueword32(&sem->_count, 0, &count, USEM_HAS_WAITERS);
3685                 if (rv == 0)
3686                         break;
3687                 umtxq_lock(&uq->uq_key);
3688                 umtxq_unbusy(&uq->uq_key);
3689                 umtxq_remove(uq);
3690                 umtxq_unlock(&uq->uq_key);
3691                 umtx_key_release(&uq->uq_key);
3692                 if (rv == -1)
3693                         return (EFAULT);
3694                 rv = thread_check_susp(td, true);
3695                 if (rv != 0)
3696                         return (rv);
3697                 goto again;
3698         }
3699         umtxq_lock(&uq->uq_key);
3700         umtxq_unbusy(&uq->uq_key);
3701
3702         error = umtxq_sleep(uq, "usem", timeout == NULL ? NULL : &timo);
3703
3704         if ((uq->uq_flags & UQF_UMTXQ) == 0)
3705                 error = 0;
3706         else {
3707                 umtxq_remove(uq);
3708                 if (timeout != NULL && (timeout->_flags & UMTX_ABSTIME) == 0) {
3709                         /* A relative timeout cannot be restarted. */
3710                         if (error == ERESTART)
3711                                 error = EINTR;
3712                         if (error == EINTR) {
3713                                 abs_timeout_update(&timo);
3714                                 timespecsub(&timo.end, &timo.cur,
3715                                     &timeout->_timeout);
3716                         }
3717                 }
3718         }
3719         umtxq_unlock(&uq->uq_key);
3720         umtx_key_release(&uq->uq_key);
3721         return (error);
3722 }
3723
3724 /*
3725  * Signal a userland semaphore.
3726  */
3727 static int
3728 do_sem2_wake(struct thread *td, struct _usem2 *sem)
3729 {
3730         struct umtx_key key;
3731         int error, cnt, rv;
3732         uint32_t count, flags;
3733
3734         rv = fueword32(&sem->_flags, &flags);
3735         if (rv == -1)
3736                 return (EFAULT);
3737         if ((error = umtx_key_get(sem, TYPE_SEM, GET_SHARE(flags), &key)) != 0)
3738                 return (error);
3739         umtxq_lock(&key);
3740         umtxq_busy(&key);
3741         cnt = umtxq_count(&key);
3742         if (cnt > 0) {
3743                 /*
3744                  * If this was the last sleeping thread, clear the waiters
3745                  * flag in _count.
3746                  */
3747                 if (cnt == 1) {
3748                         umtxq_unlock(&key);
3749                         rv = fueword32(&sem->_count, &count);
3750                         while (rv != -1 && count & USEM_HAS_WAITERS) {
3751                                 rv = casueword32(&sem->_count, count, &count,
3752                                     count & ~USEM_HAS_WAITERS);
3753                                 if (rv == 1) {
3754                                         rv = thread_check_susp(td, true);
3755                                         if (rv != 0)
3756                                                 break;
3757                                 }
3758                         }
3759                         if (rv == -1)
3760                                 error = EFAULT;
3761                         else if (rv > 0) {
3762                                 error = rv;
3763                         }
3764                         umtxq_lock(&key);
3765                 }
3766
3767                 umtxq_signal(&key, 1);
3768         }
3769         umtxq_unbusy(&key);
3770         umtxq_unlock(&key);
3771         umtx_key_release(&key);
3772         return (error);
3773 }
3774
3775 #ifdef COMPAT_FREEBSD10
3776 int
3777 freebsd10__umtx_lock(struct thread *td, struct freebsd10__umtx_lock_args *uap)
3778 {
3779         return (do_lock_umtx(td, uap->umtx, td->td_tid, 0));
3780 }
3781
3782 int
3783 freebsd10__umtx_unlock(struct thread *td,
3784     struct freebsd10__umtx_unlock_args *uap)
3785 {
3786         return (do_unlock_umtx(td, uap->umtx, td->td_tid));
3787 }
3788 #endif
3789
3790 inline int
3791 umtx_copyin_timeout(const void *uaddr, struct timespec *tsp)
3792 {
3793         int error;
3794
3795         error = copyin(uaddr, tsp, sizeof(*tsp));
3796         if (error == 0) {
3797                 if (tsp->tv_sec < 0 ||
3798                     tsp->tv_nsec >= 1000000000 ||
3799                     tsp->tv_nsec < 0)
3800                         error = EINVAL;
3801         }
3802         return (error);
3803 }
3804
3805 static inline int
3806 umtx_copyin_umtx_time(const void *uaddr, size_t size, struct _umtx_time *tp)
3807 {
3808         int error;
3809
3810         if (size <= sizeof(tp->_timeout)) {
3811                 tp->_clockid = CLOCK_REALTIME;
3812                 tp->_flags = 0;
3813                 error = copyin(uaddr, &tp->_timeout, sizeof(tp->_timeout));
3814         } else
3815                 error = copyin(uaddr, tp, sizeof(*tp));
3816         if (error != 0)
3817                 return (error);
3818         if (tp->_timeout.tv_sec < 0 ||
3819             tp->_timeout.tv_nsec >= 1000000000 || tp->_timeout.tv_nsec < 0)
3820                 return (EINVAL);
3821         return (0);
3822 }
3823
3824 static int
3825 umtx_copyin_robust_lists(const void *uaddr, size_t size,
3826     struct umtx_robust_lists_params *rb)
3827 {
3828
3829         if (size > sizeof(*rb))
3830                 return (EINVAL);
3831         return (copyin(uaddr, rb, size));
3832 }
3833
3834 static int
3835 umtx_copyout_timeout(void *uaddr, size_t sz, struct timespec *tsp)
3836 {
3837
3838         /*
3839          * Should be guaranteed by the caller, sz == uaddr1 - sizeof(_umtx_time)
3840          * and we're only called if sz >= sizeof(timespec) as supplied in the
3841          * copyops.
3842          */
3843         KASSERT(sz >= sizeof(*tsp),
3844             ("umtx_copyops specifies incorrect sizes"));
3845
3846         return (copyout(tsp, uaddr, sizeof(*tsp)));
3847 }
3848
3849 #ifdef COMPAT_FREEBSD10
3850 static int
3851 __umtx_op_lock_umtx(struct thread *td, struct _umtx_op_args *uap,
3852     const struct umtx_copyops *ops)
3853 {
3854         struct timespec *ts, timeout;
3855         int error;
3856
3857         /* Allow a null timespec (wait forever). */
3858         if (uap->uaddr2 == NULL)
3859                 ts = NULL;
3860         else {
3861                 error = ops->copyin_timeout(uap->uaddr2, &timeout);
3862                 if (error != 0)
3863                         return (error);
3864                 ts = &timeout;
3865         }
3866 #ifdef COMPAT_FREEBSD32
3867         if (ops->compat32)
3868                 return (do_lock_umtx32(td, uap->obj, uap->val, ts));
3869 #endif
3870         return (do_lock_umtx(td, uap->obj, uap->val, ts));
3871 }
3872
3873 static int
3874 __umtx_op_unlock_umtx(struct thread *td, struct _umtx_op_args *uap,
3875     const struct umtx_copyops *ops)
3876 {
3877 #ifdef COMPAT_FREEBSD32
3878         if (ops->compat32)
3879                 return (do_unlock_umtx32(td, uap->obj, uap->val));
3880 #endif
3881         return (do_unlock_umtx(td, uap->obj, uap->val));
3882 }
3883 #endif  /* COMPAT_FREEBSD10 */
3884
3885 #if !defined(COMPAT_FREEBSD10)
3886 static int
3887 __umtx_op_unimpl(struct thread *td __unused, struct _umtx_op_args *uap __unused,
3888     const struct umtx_copyops *ops __unused)
3889 {
3890         return (EOPNOTSUPP);
3891 }
3892 #endif  /* COMPAT_FREEBSD10 */
3893
3894 static int
3895 __umtx_op_wait(struct thread *td, struct _umtx_op_args *uap,
3896     const struct umtx_copyops *ops)
3897 {
3898         struct _umtx_time timeout, *tm_p;
3899         int error;
3900
3901         if (uap->uaddr2 == NULL)
3902                 tm_p = NULL;
3903         else {
3904                 error = ops->copyin_umtx_time(
3905                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
3906                 if (error != 0)
3907                         return (error);
3908                 tm_p = &timeout;
3909         }
3910         return (do_wait(td, uap->obj, uap->val, tm_p, ops->compat32, 0));
3911 }
3912
3913 static int
3914 __umtx_op_wait_uint(struct thread *td, struct _umtx_op_args *uap,
3915     const struct umtx_copyops *ops)
3916 {
3917         struct _umtx_time timeout, *tm_p;
3918         int error;
3919
3920         if (uap->uaddr2 == NULL)
3921                 tm_p = NULL;
3922         else {
3923                 error = ops->copyin_umtx_time(
3924                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
3925                 if (error != 0)
3926                         return (error);
3927                 tm_p = &timeout;
3928         }
3929         return (do_wait(td, uap->obj, uap->val, tm_p, 1, 0));
3930 }
3931
3932 static int
3933 __umtx_op_wait_uint_private(struct thread *td, struct _umtx_op_args *uap,
3934     const struct umtx_copyops *ops)
3935 {
3936         struct _umtx_time *tm_p, timeout;
3937         int error;
3938
3939         if (uap->uaddr2 == NULL)
3940                 tm_p = NULL;
3941         else {
3942                 error = ops->copyin_umtx_time(
3943                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
3944                 if (error != 0)
3945                         return (error);
3946                 tm_p = &timeout;
3947         }
3948         return (do_wait(td, uap->obj, uap->val, tm_p, 1, 1));
3949 }
3950
3951 static int
3952 __umtx_op_wake(struct thread *td, struct _umtx_op_args *uap,
3953     const struct umtx_copyops *ops __unused)
3954 {
3955
3956         return (kern_umtx_wake(td, uap->obj, uap->val, 0));
3957 }
3958
3959 #define BATCH_SIZE      128
3960 static int
3961 __umtx_op_nwake_private_native(struct thread *td, struct _umtx_op_args *uap)
3962 {
3963         char *uaddrs[BATCH_SIZE], **upp;
3964         int count, error, i, pos, tocopy;
3965
3966         upp = (char **)uap->obj;
3967         error = 0;
3968         for (count = uap->val, pos = 0; count > 0; count -= tocopy,
3969             pos += tocopy) {
3970                 tocopy = MIN(count, BATCH_SIZE);
3971                 error = copyin(upp + pos, uaddrs, tocopy * sizeof(char *));
3972                 if (error != 0)
3973                         break;
3974                 for (i = 0; i < tocopy; ++i) {
3975                         kern_umtx_wake(td, uaddrs[i], INT_MAX, 1);
3976                 }
3977                 maybe_yield();
3978         }
3979         return (error);
3980 }
3981
3982 static int
3983 __umtx_op_nwake_private_compat32(struct thread *td, struct _umtx_op_args *uap)
3984 {
3985         uint32_t uaddrs[BATCH_SIZE], *upp;
3986         int count, error, i, pos, tocopy;
3987
3988         upp = (uint32_t *)uap->obj;
3989         error = 0;
3990         for (count = uap->val, pos = 0; count > 0; count -= tocopy,
3991             pos += tocopy) {
3992                 tocopy = MIN(count, BATCH_SIZE);
3993                 error = copyin(upp + pos, uaddrs, tocopy * sizeof(uint32_t));
3994                 if (error != 0)
3995                         break;
3996                 for (i = 0; i < tocopy; ++i) {
3997                         kern_umtx_wake(td, (void *)(uintptr_t)uaddrs[i],
3998                             INT_MAX, 1);
3999                 }
4000                 maybe_yield();
4001         }
4002         return (error);
4003 }
4004
4005 static int
4006 __umtx_op_nwake_private(struct thread *td, struct _umtx_op_args *uap,
4007     const struct umtx_copyops *ops)
4008 {
4009
4010         if (ops->compat32)
4011                 return (__umtx_op_nwake_private_compat32(td, uap));
4012         return (__umtx_op_nwake_private_native(td, uap));
4013 }
4014
4015 static int
4016 __umtx_op_wake_private(struct thread *td, struct _umtx_op_args *uap,
4017     const struct umtx_copyops *ops __unused)
4018 {
4019
4020         return (kern_umtx_wake(td, uap->obj, uap->val, 1));
4021 }
4022
4023 static int
4024 __umtx_op_lock_umutex(struct thread *td, struct _umtx_op_args *uap,
4025    const struct umtx_copyops *ops)
4026 {
4027         struct _umtx_time *tm_p, timeout;
4028         int error;
4029
4030         /* Allow a null timespec (wait forever). */
4031         if (uap->uaddr2 == NULL)
4032                 tm_p = NULL;
4033         else {
4034                 error = ops->copyin_umtx_time(
4035                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
4036                 if (error != 0)
4037                         return (error);
4038                 tm_p = &timeout;
4039         }
4040         return (do_lock_umutex(td, uap->obj, tm_p, 0));
4041 }
4042
4043 static int
4044 __umtx_op_trylock_umutex(struct thread *td, struct _umtx_op_args *uap,
4045     const struct umtx_copyops *ops __unused)
4046 {
4047
4048         return (do_lock_umutex(td, uap->obj, NULL, _UMUTEX_TRY));
4049 }
4050
4051 static int
4052 __umtx_op_wait_umutex(struct thread *td, struct _umtx_op_args *uap,
4053     const struct umtx_copyops *ops)
4054 {
4055         struct _umtx_time *tm_p, timeout;
4056         int error;
4057
4058         /* Allow a null timespec (wait forever). */
4059         if (uap->uaddr2 == NULL)
4060                 tm_p = NULL;
4061         else {
4062                 error = ops->copyin_umtx_time(
4063                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
4064                 if (error != 0)
4065                         return (error);
4066                 tm_p = &timeout;
4067         }
4068         return (do_lock_umutex(td, uap->obj, tm_p, _UMUTEX_WAIT));
4069 }
4070
4071 static int
4072 __umtx_op_wake_umutex(struct thread *td, struct _umtx_op_args *uap,
4073     const struct umtx_copyops *ops __unused)
4074 {
4075
4076         return (do_wake_umutex(td, uap->obj));
4077 }
4078
4079 static int
4080 __umtx_op_unlock_umutex(struct thread *td, struct _umtx_op_args *uap,
4081     const struct umtx_copyops *ops __unused)
4082 {
4083
4084         return (do_unlock_umutex(td, uap->obj, false));
4085 }
4086
4087 static int
4088 __umtx_op_set_ceiling(struct thread *td, struct _umtx_op_args *uap,
4089     const struct umtx_copyops *ops __unused)
4090 {
4091
4092         return (do_set_ceiling(td, uap->obj, uap->val, uap->uaddr1));
4093 }
4094
4095 static int
4096 __umtx_op_cv_wait(struct thread *td, struct _umtx_op_args *uap,
4097     const struct umtx_copyops *ops)
4098 {
4099         struct timespec *ts, timeout;
4100         int error;
4101
4102         /* Allow a null timespec (wait forever). */
4103         if (uap->uaddr2 == NULL)
4104                 ts = NULL;
4105         else {
4106                 error = ops->copyin_timeout(uap->uaddr2, &timeout);
4107                 if (error != 0)
4108                         return (error);
4109                 ts = &timeout;
4110         }
4111         return (do_cv_wait(td, uap->obj, uap->uaddr1, ts, uap->val));
4112 }
4113
4114 static int
4115 __umtx_op_cv_signal(struct thread *td, struct _umtx_op_args *uap,
4116     const struct umtx_copyops *ops __unused)
4117 {
4118
4119         return (do_cv_signal(td, uap->obj));
4120 }
4121
4122 static int
4123 __umtx_op_cv_broadcast(struct thread *td, struct _umtx_op_args *uap,
4124     const struct umtx_copyops *ops __unused)
4125 {
4126
4127         return (do_cv_broadcast(td, uap->obj));
4128 }
4129
4130 static int
4131 __umtx_op_rw_rdlock(struct thread *td, struct _umtx_op_args *uap,
4132     const struct umtx_copyops *ops)
4133 {
4134         struct _umtx_time timeout;
4135         int error;
4136
4137         /* Allow a null timespec (wait forever). */
4138         if (uap->uaddr2 == NULL) {
4139                 error = do_rw_rdlock(td, uap->obj, uap->val, 0);
4140         } else {
4141                 error = ops->copyin_umtx_time(uap->uaddr2,
4142                    (size_t)uap->uaddr1, &timeout);
4143                 if (error != 0)
4144                         return (error);
4145                 error = do_rw_rdlock(td, uap->obj, uap->val, &timeout);
4146         }
4147         return (error);
4148 }
4149
4150 static int
4151 __umtx_op_rw_wrlock(struct thread *td, struct _umtx_op_args *uap,
4152     const struct umtx_copyops *ops)
4153 {
4154         struct _umtx_time timeout;
4155         int error;
4156
4157         /* Allow a null timespec (wait forever). */
4158         if (uap->uaddr2 == NULL) {
4159                 error = do_rw_wrlock(td, uap->obj, 0);
4160         } else {
4161                 error = ops->copyin_umtx_time(uap->uaddr2,
4162                    (size_t)uap->uaddr1, &timeout);
4163                 if (error != 0)
4164                         return (error);
4165
4166                 error = do_rw_wrlock(td, uap->obj, &timeout);
4167         }
4168         return (error);
4169 }
4170
4171 static int
4172 __umtx_op_rw_unlock(struct thread *td, struct _umtx_op_args *uap,
4173     const struct umtx_copyops *ops __unused)
4174 {
4175
4176         return (do_rw_unlock(td, uap->obj));
4177 }
4178
4179 #if defined(COMPAT_FREEBSD9) || defined(COMPAT_FREEBSD10)
4180 static int
4181 __umtx_op_sem_wait(struct thread *td, struct _umtx_op_args *uap,
4182     const struct umtx_copyops *ops)
4183 {
4184         struct _umtx_time *tm_p, timeout;
4185         int error;
4186
4187         /* Allow a null timespec (wait forever). */
4188         if (uap->uaddr2 == NULL)
4189                 tm_p = NULL;
4190         else {
4191                 error = ops->copyin_umtx_time(
4192                     uap->uaddr2, (size_t)uap->uaddr1, &timeout);
4193                 if (error != 0)
4194                         return (error);
4195                 tm_p = &timeout;
4196         }
4197         return (do_sem_wait(td, uap->obj, tm_p));
4198 }
4199
4200 static int
4201 __umtx_op_sem_wake(struct thread *td, struct _umtx_op_args *uap,
4202     const struct umtx_copyops *ops __unused)
4203 {
4204
4205         return (do_sem_wake(td, uap->obj));
4206 }
4207 #endif
4208
4209 static int
4210 __umtx_op_wake2_umutex(struct thread *td, struct _umtx_op_args *uap,
4211     const struct umtx_copyops *ops __unused)
4212 {
4213
4214         return (do_wake2_umutex(td, uap->obj, uap->val));
4215 }
4216
4217 static int
4218 __umtx_op_sem2_wait(struct thread *td, struct _umtx_op_args *uap,
4219     const struct umtx_copyops *ops)
4220 {
4221         struct _umtx_time *tm_p, timeout;
4222         size_t uasize;
4223         int error;
4224
4225         /* Allow a null timespec (wait forever). */
4226         if (uap->uaddr2 == NULL) {
4227                 uasize = 0;
4228                 tm_p = NULL;
4229         } else {
4230                 uasize = (size_t)uap->uaddr1;
4231                 error = ops->copyin_umtx_time(uap->uaddr2, uasize, &timeout);
4232                 if (error != 0)
4233                         return (error);
4234                 tm_p = &timeout;
4235         }
4236         error = do_sem2_wait(td, uap->obj, tm_p);
4237         if (error == EINTR && uap->uaddr2 != NULL &&
4238             (timeout._flags & UMTX_ABSTIME) == 0 &&
4239             uasize >= ops->umtx_time_sz + ops->timespec_sz) {
4240                 error = ops->copyout_timeout(
4241                     (void *)((uintptr_t)uap->uaddr2 + ops->umtx_time_sz),
4242                     uasize - ops->umtx_time_sz, &timeout._timeout);
4243                 if (error == 0) {
4244                         error = EINTR;
4245                 }
4246         }
4247
4248         return (error);
4249 }
4250
4251 static int
4252 __umtx_op_sem2_wake(struct thread *td, struct _umtx_op_args *uap,
4253     const struct umtx_copyops *ops __unused)
4254 {
4255
4256         return (do_sem2_wake(td, uap->obj));
4257 }
4258
4259 #define USHM_OBJ_UMTX(o)                                                \
4260     ((struct umtx_shm_obj_list *)(&(o)->umtx_data))
4261
4262 #define USHMF_REG_LINKED        0x0001
4263 #define USHMF_OBJ_LINKED        0x0002
4264 struct umtx_shm_reg {
4265         TAILQ_ENTRY(umtx_shm_reg) ushm_reg_link;
4266         LIST_ENTRY(umtx_shm_reg) ushm_obj_link;
4267         struct umtx_key         ushm_key;
4268         struct ucred            *ushm_cred;
4269         struct shmfd            *ushm_obj;
4270         u_int                   ushm_refcnt;
4271         u_int                   ushm_flags;
4272 };
4273
4274 LIST_HEAD(umtx_shm_obj_list, umtx_shm_reg);
4275 TAILQ_HEAD(umtx_shm_reg_head, umtx_shm_reg);
4276
4277 static uma_zone_t umtx_shm_reg_zone;
4278 static struct umtx_shm_reg_head umtx_shm_registry[UMTX_CHAINS];
4279 static struct mtx umtx_shm_lock;
4280 static struct umtx_shm_reg_head umtx_shm_reg_delfree =
4281     TAILQ_HEAD_INITIALIZER(umtx_shm_reg_delfree);
4282
4283 static void umtx_shm_free_reg(struct umtx_shm_reg *reg);
4284
4285 static void
4286 umtx_shm_reg_delfree_tq(void *context __unused, int pending __unused)
4287 {
4288         struct umtx_shm_reg_head d;
4289         struct umtx_shm_reg *reg, *reg1;
4290
4291         TAILQ_INIT(&d);
4292         mtx_lock(&umtx_shm_lock);
4293         TAILQ_CONCAT(&d, &umtx_shm_reg_delfree, ushm_reg_link);
4294         mtx_unlock(&umtx_shm_lock);
4295         TAILQ_FOREACH_SAFE(reg, &d, ushm_reg_link, reg1) {
4296                 TAILQ_REMOVE(&d, reg, ushm_reg_link);
4297                 umtx_shm_free_reg(reg);
4298         }
4299 }
4300
4301 static struct task umtx_shm_reg_delfree_task =
4302     TASK_INITIALIZER(0, umtx_shm_reg_delfree_tq, NULL);
4303
4304 static struct umtx_shm_reg *
4305 umtx_shm_find_reg_locked(const struct umtx_key *key)
4306 {
4307         struct umtx_shm_reg *reg;
4308         struct umtx_shm_reg_head *reg_head;
4309
4310         KASSERT(key->shared, ("umtx_p_find_rg: private key"));
4311         mtx_assert(&umtx_shm_lock, MA_OWNED);
4312         reg_head = &umtx_shm_registry[key->hash];
4313         TAILQ_FOREACH(reg, reg_head, ushm_reg_link) {
4314                 KASSERT(reg->ushm_key.shared,
4315                     ("non-shared key on reg %p %d", reg, reg->ushm_key.shared));
4316                 if (reg->ushm_key.info.shared.object ==
4317                     key->info.shared.object &&
4318                     reg->ushm_key.info.shared.offset ==
4319                     key->info.shared.offset) {
4320                         KASSERT(reg->ushm_key.type == TYPE_SHM, ("TYPE_USHM"));
4321                         KASSERT(reg->ushm_refcnt > 0,
4322                             ("reg %p refcnt 0 onlist", reg));
4323                         KASSERT((reg->ushm_flags & USHMF_REG_LINKED) != 0,
4324                             ("reg %p not linked", reg));
4325                         reg->ushm_refcnt++;
4326                         return (reg);
4327                 }
4328         }
4329         return (NULL);
4330 }
4331
4332 static struct umtx_shm_reg *
4333 umtx_shm_find_reg(const struct umtx_key *key)
4334 {
4335         struct umtx_shm_reg *reg;
4336
4337         mtx_lock(&umtx_shm_lock);
4338         reg = umtx_shm_find_reg_locked(key);
4339         mtx_unlock(&umtx_shm_lock);
4340         return (reg);
4341 }
4342
4343 static void
4344 umtx_shm_free_reg(struct umtx_shm_reg *reg)
4345 {
4346
4347         chgumtxcnt(reg->ushm_cred->cr_ruidinfo, -1, 0);
4348         crfree(reg->ushm_cred);
4349         shm_drop(reg->ushm_obj);
4350         uma_zfree(umtx_shm_reg_zone, reg);
4351 }
4352
4353 static bool
4354 umtx_shm_unref_reg_locked(struct umtx_shm_reg *reg, bool force)
4355 {
4356         bool res;
4357
4358         mtx_assert(&umtx_shm_lock, MA_OWNED);
4359         KASSERT(reg->ushm_refcnt > 0, ("ushm_reg %p refcnt 0", reg));
4360         reg->ushm_refcnt--;
4361         res = reg->ushm_refcnt == 0;
4362         if (res || force) {
4363                 if ((reg->ushm_flags & USHMF_REG_LINKED) != 0) {
4364                         TAILQ_REMOVE(&umtx_shm_registry[reg->ushm_key.hash],
4365                             reg, ushm_reg_link);
4366                         reg->ushm_flags &= ~USHMF_REG_LINKED;
4367                 }
4368                 if ((reg->ushm_flags & USHMF_OBJ_LINKED) != 0) {
4369                         LIST_REMOVE(reg, ushm_obj_link);
4370                         reg->ushm_flags &= ~USHMF_OBJ_LINKED;
4371                 }
4372         }
4373         return (res);
4374 }
4375
4376 static void
4377 umtx_shm_unref_reg(struct umtx_shm_reg *reg, bool force)
4378 {
4379         vm_object_t object;
4380         bool dofree;
4381
4382         if (force) {
4383                 object = reg->ushm_obj->shm_object;
4384                 VM_OBJECT_WLOCK(object);
4385                 object->flags |= OBJ_UMTXDEAD;
4386                 VM_OBJECT_WUNLOCK(object);
4387         }
4388         mtx_lock(&umtx_shm_lock);
4389         dofree = umtx_shm_unref_reg_locked(reg, force);
4390         mtx_unlock(&umtx_shm_lock);
4391         if (dofree)
4392                 umtx_shm_free_reg(reg);
4393 }
4394
4395 void
4396 umtx_shm_object_init(vm_object_t object)
4397 {
4398
4399         LIST_INIT(USHM_OBJ_UMTX(object));
4400 }
4401
4402 void
4403 umtx_shm_object_terminated(vm_object_t object)
4404 {
4405         struct umtx_shm_reg *reg, *reg1;
4406         bool dofree;
4407
4408         if (LIST_EMPTY(USHM_OBJ_UMTX(object)))
4409                 return;
4410
4411         dofree = false;
4412         mtx_lock(&umtx_shm_lock);
4413         LIST_FOREACH_SAFE(reg, USHM_OBJ_UMTX(object), ushm_obj_link, reg1) {
4414                 if (umtx_shm_unref_reg_locked(reg, true)) {
4415                         TAILQ_INSERT_TAIL(&umtx_shm_reg_delfree, reg,
4416                             ushm_reg_link);
4417                         dofree = true;
4418                 }
4419         }
4420         mtx_unlock(&umtx_shm_lock);
4421         if (dofree)
4422                 taskqueue_enqueue(taskqueue_thread, &umtx_shm_reg_delfree_task);
4423 }
4424
4425 static int
4426 umtx_shm_create_reg(struct thread *td, const struct umtx_key *key,
4427     struct umtx_shm_reg **res)
4428 {
4429         struct umtx_shm_reg *reg, *reg1;
4430         struct ucred *cred;
4431         int error;
4432
4433         reg = umtx_shm_find_reg(key);
4434         if (reg != NULL) {
4435                 *res = reg;
4436                 return (0);
4437         }
4438         cred = td->td_ucred;
4439         if (!chgumtxcnt(cred->cr_ruidinfo, 1, lim_cur(td, RLIMIT_UMTXP)))
4440                 return (ENOMEM);
4441         reg = uma_zalloc(umtx_shm_reg_zone, M_WAITOK | M_ZERO);
4442         reg->ushm_refcnt = 1;
4443         bcopy(key, &reg->ushm_key, sizeof(*key));
4444         reg->ushm_obj = shm_alloc(td->td_ucred, O_RDWR, false);
4445         reg->ushm_cred = crhold(cred);
4446         error = shm_dotruncate(reg->ushm_obj, PAGE_SIZE);
4447         if (error != 0) {
4448                 umtx_shm_free_reg(reg);
4449                 return (error);
4450         }
4451         mtx_lock(&umtx_shm_lock);
4452         reg1 = umtx_shm_find_reg_locked(key);
4453         if (reg1 != NULL) {
4454                 mtx_unlock(&umtx_shm_lock);
4455                 umtx_shm_free_reg(reg);
4456                 *res = reg1;
4457                 return (0);
4458         }
4459         reg->ushm_refcnt++;
4460         TAILQ_INSERT_TAIL(&umtx_shm_registry[key->hash], reg, ushm_reg_link);
4461         LIST_INSERT_HEAD(USHM_OBJ_UMTX(key->info.shared.object), reg,
4462             ushm_obj_link);
4463         reg->ushm_flags = USHMF_REG_LINKED | USHMF_OBJ_LINKED;
4464         mtx_unlock(&umtx_shm_lock);
4465         *res = reg;
4466         return (0);
4467 }
4468
4469 static int
4470 umtx_shm_alive(struct thread *td, void *addr)
4471 {
4472         vm_map_t map;
4473         vm_map_entry_t entry;
4474         vm_object_t object;
4475         vm_pindex_t pindex;
4476         vm_prot_t prot;
4477         int res, ret;
4478         boolean_t wired;
4479
4480         map = &td->td_proc->p_vmspace->vm_map;
4481         res = vm_map_lookup(&map, (uintptr_t)addr, VM_PROT_READ, &entry,
4482             &object, &pindex, &prot, &wired);
4483         if (res != KERN_SUCCESS)
4484                 return (EFAULT);
4485         if (object == NULL)
4486                 ret = EINVAL;
4487         else
4488                 ret = (object->flags & OBJ_UMTXDEAD) != 0 ? ENOTTY : 0;
4489         vm_map_lookup_done(map, entry);
4490         return (ret);
4491 }
4492
4493 static void
4494 umtx_shm_init(void)
4495 {
4496         int i;
4497
4498         umtx_shm_reg_zone = uma_zcreate("umtx_shm", sizeof(struct umtx_shm_reg),
4499             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
4500         mtx_init(&umtx_shm_lock, "umtxshm", NULL, MTX_DEF);
4501         for (i = 0; i < nitems(umtx_shm_registry); i++)
4502                 TAILQ_INIT(&umtx_shm_registry[i]);
4503 }
4504
4505 static int
4506 umtx_shm(struct thread *td, void *addr, u_int flags)
4507 {
4508         struct umtx_key key;
4509         struct umtx_shm_reg *reg;
4510         struct file *fp;
4511         int error, fd;
4512
4513         if (__bitcount(flags & (UMTX_SHM_CREAT | UMTX_SHM_LOOKUP |
4514             UMTX_SHM_DESTROY| UMTX_SHM_ALIVE)) != 1)
4515                 return (EINVAL);
4516         if ((flags & UMTX_SHM_ALIVE) != 0)
4517                 return (umtx_shm_alive(td, addr));
4518         error = umtx_key_get(addr, TYPE_SHM, PROCESS_SHARE, &key);
4519         if (error != 0)
4520                 return (error);
4521         KASSERT(key.shared == 1, ("non-shared key"));
4522         if ((flags & UMTX_SHM_CREAT) != 0) {
4523                 error = umtx_shm_create_reg(td, &key, &reg);
4524         } else {
4525                 reg = umtx_shm_find_reg(&key);
4526                 if (reg == NULL)
4527                         error = ESRCH;
4528         }
4529         umtx_key_release(&key);
4530         if (error != 0)
4531                 return (error);
4532         KASSERT(reg != NULL, ("no reg"));
4533         if ((flags & UMTX_SHM_DESTROY) != 0) {
4534                 umtx_shm_unref_reg(reg, true);
4535         } else {
4536 #if 0
4537 #ifdef MAC
4538                 error = mac_posixshm_check_open(td->td_ucred,
4539                     reg->ushm_obj, FFLAGS(O_RDWR));
4540                 if (error == 0)
4541 #endif
4542                         error = shm_access(reg->ushm_obj, td->td_ucred,
4543                             FFLAGS(O_RDWR));
4544                 if (error == 0)
4545 #endif
4546                         error = falloc_caps(td, &fp, &fd, O_CLOEXEC, NULL);
4547                 if (error == 0) {
4548                         shm_hold(reg->ushm_obj);
4549                         finit(fp, FFLAGS(O_RDWR), DTYPE_SHM, reg->ushm_obj,
4550                             &shm_ops);
4551                         td->td_retval[0] = fd;
4552                         fdrop(fp, td);
4553                 }
4554         }
4555         umtx_shm_unref_reg(reg, false);
4556         return (error);
4557 }
4558
4559 static int
4560 __umtx_op_shm(struct thread *td, struct _umtx_op_args *uap,
4561     const struct umtx_copyops *ops __unused)
4562 {
4563
4564         return (umtx_shm(td, uap->uaddr1, uap->val));
4565 }
4566
4567 static int
4568 __umtx_op_robust_lists(struct thread *td, struct _umtx_op_args *uap,
4569     const struct umtx_copyops *ops)
4570 {
4571         struct umtx_robust_lists_params rb;
4572         int error;
4573
4574         if (ops->compat32) {
4575                 if ((td->td_pflags2 & TDP2_COMPAT32RB) == 0 &&
4576                     (td->td_rb_list != 0 || td->td_rbp_list != 0 ||
4577                     td->td_rb_inact != 0))
4578                         return (EBUSY);
4579         } else if ((td->td_pflags2 & TDP2_COMPAT32RB) != 0) {
4580                 return (EBUSY);
4581         }
4582
4583         bzero(&rb, sizeof(rb));
4584         error = ops->copyin_robust_lists(uap->uaddr1, uap->val, &rb);
4585         if (error != 0)
4586                 return (error);
4587
4588         if (ops->compat32)
4589                 td->td_pflags2 |= TDP2_COMPAT32RB;
4590
4591         td->td_rb_list = rb.robust_list_offset;
4592         td->td_rbp_list = rb.robust_priv_list_offset;
4593         td->td_rb_inact = rb.robust_inact_offset;
4594         return (0);
4595 }
4596
4597 #if defined(__i386__) || defined(__amd64__)
4598 /*
4599  * Provide the standard 32-bit definitions for x86, since native/compat32 use a
4600  * 32-bit time_t there.  Other architectures just need the i386 definitions
4601  * along with their standard compat32.
4602  */
4603 struct timespecx32 {
4604         int64_t                 tv_sec;
4605         int32_t                 tv_nsec;
4606 };
4607
4608 struct umtx_timex32 {
4609         struct  timespecx32     _timeout;
4610         uint32_t                _flags;
4611         uint32_t                _clockid;
4612 };
4613
4614 #ifndef __i386__
4615 #define timespeci386    timespec32
4616 #define umtx_timei386   umtx_time32
4617 #endif
4618 #else /* !__i386__ && !__amd64__ */
4619 /* 32-bit architectures can emulate i386, so define these almost everywhere. */
4620 struct timespeci386 {
4621         int32_t                 tv_sec;
4622         int32_t                 tv_nsec;
4623 };
4624
4625 struct umtx_timei386 {
4626         struct  timespeci386    _timeout;
4627         uint32_t                _flags;
4628         uint32_t                _clockid;
4629 };
4630
4631 #if defined(__LP64__)
4632 #define timespecx32     timespec32
4633 #define umtx_timex32    umtx_time32
4634 #endif
4635 #endif
4636
4637 static int
4638 umtx_copyin_robust_lists32(const void *uaddr, size_t size,
4639     struct umtx_robust_lists_params *rbp)
4640 {
4641         struct umtx_robust_lists_params_compat32 rb32;
4642         int error;
4643
4644         if (size > sizeof(rb32))
4645                 return (EINVAL);
4646         bzero(&rb32, sizeof(rb32));
4647         error = copyin(uaddr, &rb32, size);
4648         if (error != 0)
4649                 return (error);
4650         CP(rb32, *rbp, robust_list_offset);
4651         CP(rb32, *rbp, robust_priv_list_offset);
4652         CP(rb32, *rbp, robust_inact_offset);
4653         return (0);
4654 }
4655
4656 #ifndef __i386__
4657 static inline int
4658 umtx_copyin_timeouti386(const void *uaddr, struct timespec *tsp)
4659 {
4660         struct timespeci386 ts32;
4661         int error;
4662
4663         error = copyin(uaddr, &ts32, sizeof(ts32));
4664         if (error == 0) {
4665                 if (ts32.tv_sec < 0 ||
4666                     ts32.tv_nsec >= 1000000000 ||
4667                     ts32.tv_nsec < 0)
4668                         error = EINVAL;
4669                 else {
4670                         CP(ts32, *tsp, tv_sec);
4671                         CP(ts32, *tsp, tv_nsec);
4672                 }
4673         }
4674         return (error);
4675 }
4676
4677 static inline int
4678 umtx_copyin_umtx_timei386(const void *uaddr, size_t size, struct _umtx_time *tp)
4679 {
4680         struct umtx_timei386 t32;
4681         int error;
4682
4683         t32._clockid = CLOCK_REALTIME;
4684         t32._flags   = 0;
4685         if (size <= sizeof(t32._timeout))
4686                 error = copyin(uaddr, &t32._timeout, sizeof(t32._timeout));
4687         else
4688                 error = copyin(uaddr, &t32, sizeof(t32));
4689         if (error != 0)
4690                 return (error);
4691         if (t32._timeout.tv_sec < 0 ||
4692             t32._timeout.tv_nsec >= 1000000000 || t32._timeout.tv_nsec < 0)
4693                 return (EINVAL);
4694         TS_CP(t32, *tp, _timeout);
4695         CP(t32, *tp, _flags);
4696         CP(t32, *tp, _clockid);
4697         return (0);
4698 }
4699
4700 static int
4701 umtx_copyout_timeouti386(void *uaddr, size_t sz, struct timespec *tsp)
4702 {
4703         struct timespeci386 remain32 = {
4704                 .tv_sec = tsp->tv_sec,
4705                 .tv_nsec = tsp->tv_nsec,
4706         };
4707
4708         /*
4709          * Should be guaranteed by the caller, sz == uaddr1 - sizeof(_umtx_time)
4710          * and we're only called if sz >= sizeof(timespec) as supplied in the
4711          * copyops.
4712          */
4713         KASSERT(sz >= sizeof(remain32),
4714             ("umtx_copyops specifies incorrect sizes"));
4715
4716         return (copyout(&remain32, uaddr, sizeof(remain32)));
4717 }
4718 #endif /* !__i386__ */
4719
4720 #if defined(__i386__) || defined(__LP64__)
4721 static inline int
4722 umtx_copyin_timeoutx32(const void *uaddr, struct timespec *tsp)
4723 {
4724         struct timespecx32 ts32;
4725         int error;
4726
4727         error = copyin(uaddr, &ts32, sizeof(ts32));
4728         if (error == 0) {
4729                 if (ts32.tv_sec < 0 ||
4730                     ts32.tv_nsec >= 1000000000 ||
4731                     ts32.tv_nsec < 0)
4732                         error = EINVAL;
4733                 else {
4734                         CP(ts32, *tsp, tv_sec);
4735                         CP(ts32, *tsp, tv_nsec);
4736                 }
4737         }
4738         return (error);
4739 }
4740
4741 static inline int
4742 umtx_copyin_umtx_timex32(const void *uaddr, size_t size, struct _umtx_time *tp)
4743 {
4744         struct umtx_timex32 t32;
4745         int error;
4746
4747         t32._clockid = CLOCK_REALTIME;
4748         t32._flags   = 0;
4749         if (size <= sizeof(t32._timeout))
4750                 error = copyin(uaddr, &t32._timeout, sizeof(t32._timeout));
4751         else
4752                 error = copyin(uaddr, &t32, sizeof(t32));
4753         if (error != 0)
4754                 return (error);
4755         if (t32._timeout.tv_sec < 0 ||
4756             t32._timeout.tv_nsec >= 1000000000 || t32._timeout.tv_nsec < 0)
4757                 return (EINVAL);
4758         TS_CP(t32, *tp, _timeout);
4759         CP(t32, *tp, _flags);
4760         CP(t32, *tp, _clockid);
4761         return (0);
4762 }
4763
4764 static int
4765 umtx_copyout_timeoutx32(void *uaddr, size_t sz, struct timespec *tsp)
4766 {
4767         struct timespecx32 remain32 = {
4768                 .tv_sec = tsp->tv_sec,
4769                 .tv_nsec = tsp->tv_nsec,
4770         };
4771
4772         /*
4773          * Should be guaranteed by the caller, sz == uaddr1 - sizeof(_umtx_time)
4774          * and we're only called if sz >= sizeof(timespec) as supplied in the
4775          * copyops.
4776          */
4777         KASSERT(sz >= sizeof(remain32),
4778             ("umtx_copyops specifies incorrect sizes"));
4779
4780         return (copyout(&remain32, uaddr, sizeof(remain32)));
4781 }
4782 #endif /* __i386__ || __LP64__ */
4783
4784 typedef int (*_umtx_op_func)(struct thread *td, struct _umtx_op_args *uap,
4785     const struct umtx_copyops *umtx_ops);
4786
4787 static const _umtx_op_func op_table[] = {
4788 #ifdef COMPAT_FREEBSD10
4789         [UMTX_OP_LOCK]          = __umtx_op_lock_umtx,
4790         [UMTX_OP_UNLOCK]        = __umtx_op_unlock_umtx,
4791 #else
4792         [UMTX_OP_LOCK]          = __umtx_op_unimpl,
4793         [UMTX_OP_UNLOCK]        = __umtx_op_unimpl,
4794 #endif
4795         [UMTX_OP_WAIT]          = __umtx_op_wait,
4796         [UMTX_OP_WAKE]          = __umtx_op_wake,
4797         [UMTX_OP_MUTEX_TRYLOCK] = __umtx_op_trylock_umutex,
4798         [UMTX_OP_MUTEX_LOCK]    = __umtx_op_lock_umutex,
4799         [UMTX_OP_MUTEX_UNLOCK]  = __umtx_op_unlock_umutex,
4800         [UMTX_OP_SET_CEILING]   = __umtx_op_set_ceiling,
4801         [UMTX_OP_CV_WAIT]       = __umtx_op_cv_wait,
4802         [UMTX_OP_CV_SIGNAL]     = __umtx_op_cv_signal,
4803         [UMTX_OP_CV_BROADCAST]  = __umtx_op_cv_broadcast,
4804         [UMTX_OP_WAIT_UINT]     = __umtx_op_wait_uint,
4805         [UMTX_OP_RW_RDLOCK]     = __umtx_op_rw_rdlock,
4806         [UMTX_OP_RW_WRLOCK]     = __umtx_op_rw_wrlock,
4807         [UMTX_OP_RW_UNLOCK]     = __umtx_op_rw_unlock,
4808         [UMTX_OP_WAIT_UINT_PRIVATE] = __umtx_op_wait_uint_private,
4809         [UMTX_OP_WAKE_PRIVATE]  = __umtx_op_wake_private,
4810         [UMTX_OP_MUTEX_WAIT]    = __umtx_op_wait_umutex,
4811         [UMTX_OP_MUTEX_WAKE]    = __umtx_op_wake_umutex,
4812 #if defined(COMPAT_FREEBSD9) || defined(COMPAT_FREEBSD10)
4813         [UMTX_OP_SEM_WAIT]      = __umtx_op_sem_wait,
4814         [UMTX_OP_SEM_WAKE]      = __umtx_op_sem_wake,
4815 #else
4816         [UMTX_OP_SEM_WAIT]      = __umtx_op_unimpl,
4817         [UMTX_OP_SEM_WAKE]      = __umtx_op_unimpl,
4818 #endif
4819         [UMTX_OP_NWAKE_PRIVATE] = __umtx_op_nwake_private,
4820         [UMTX_OP_MUTEX_WAKE2]   = __umtx_op_wake2_umutex,
4821         [UMTX_OP_SEM2_WAIT]     = __umtx_op_sem2_wait,
4822         [UMTX_OP_SEM2_WAKE]     = __umtx_op_sem2_wake,
4823         [UMTX_OP_SHM]           = __umtx_op_shm,
4824         [UMTX_OP_ROBUST_LISTS]  = __umtx_op_robust_lists,
4825 };
4826
4827 static const struct umtx_copyops umtx_native_ops = {
4828         .copyin_timeout = umtx_copyin_timeout,
4829         .copyin_umtx_time = umtx_copyin_umtx_time,
4830         .copyin_robust_lists = umtx_copyin_robust_lists,
4831         .copyout_timeout = umtx_copyout_timeout,
4832         .timespec_sz = sizeof(struct timespec),
4833         .umtx_time_sz = sizeof(struct _umtx_time),
4834 };
4835
4836 #ifndef __i386__
4837 static const struct umtx_copyops umtx_native_opsi386 = {
4838         .copyin_timeout = umtx_copyin_timeouti386,
4839         .copyin_umtx_time = umtx_copyin_umtx_timei386,
4840         .copyin_robust_lists = umtx_copyin_robust_lists32,
4841         .copyout_timeout = umtx_copyout_timeouti386,
4842         .timespec_sz = sizeof(struct timespeci386),
4843         .umtx_time_sz = sizeof(struct umtx_timei386),
4844         .compat32 = true,
4845 };
4846 #endif
4847
4848 #if defined(__i386__) || defined(__LP64__)
4849 /* i386 can emulate other 32-bit archs, too! */
4850 static const struct umtx_copyops umtx_native_opsx32 = {
4851         .copyin_timeout = umtx_copyin_timeoutx32,
4852         .copyin_umtx_time = umtx_copyin_umtx_timex32,
4853         .copyin_robust_lists = umtx_copyin_robust_lists32,
4854         .copyout_timeout = umtx_copyout_timeoutx32,
4855         .timespec_sz = sizeof(struct timespecx32),
4856         .umtx_time_sz = sizeof(struct umtx_timex32),
4857         .compat32 = true,
4858 };
4859
4860 #ifdef COMPAT_FREEBSD32
4861 #ifdef __amd64__
4862 #define umtx_native_ops32       umtx_native_opsi386
4863 #else
4864 #define umtx_native_ops32       umtx_native_opsx32
4865 #endif
4866 #endif /* COMPAT_FREEBSD32 */
4867 #endif /* __i386__ || __LP64__ */
4868
4869 #define UMTX_OP__FLAGS  (UMTX_OP__32BIT | UMTX_OP__I386)
4870
4871 static int
4872 kern__umtx_op(struct thread *td, void *obj, int op, unsigned long val,
4873     void *uaddr1, void *uaddr2, const struct umtx_copyops *ops)
4874 {
4875         struct _umtx_op_args uap = {
4876                 .obj = obj,
4877                 .op = op & ~UMTX_OP__FLAGS,
4878                 .val = val,
4879                 .uaddr1 = uaddr1,
4880                 .uaddr2 = uaddr2
4881         };
4882
4883         if ((uap.op >= nitems(op_table)))
4884                 return (EINVAL);
4885         return ((*op_table[uap.op])(td, &uap, ops));
4886 }
4887
4888 int
4889 sys__umtx_op(struct thread *td, struct _umtx_op_args *uap)
4890 {
4891         static const struct umtx_copyops *umtx_ops;
4892
4893         umtx_ops = &umtx_native_ops;
4894 #ifdef __LP64__
4895         if ((uap->op & (UMTX_OP__32BIT | UMTX_OP__I386)) != 0) {
4896                 if ((uap->op & UMTX_OP__I386) != 0)
4897                         umtx_ops = &umtx_native_opsi386;
4898                 else
4899                         umtx_ops = &umtx_native_opsx32;
4900         }
4901 #elif !defined(__i386__)
4902         /* We consider UMTX_OP__32BIT a nop on !i386 ILP32. */
4903         if ((uap->op & UMTX_OP__I386) != 0)
4904                 umtx_ops = &umtx_native_opsi386;
4905 #else
4906         /* Likewise, UMTX_OP__I386 is a nop on i386. */
4907         if ((uap->op & UMTX_OP__32BIT) != 0)
4908                 umtx_ops = &umtx_native_opsx32;
4909 #endif
4910         return (kern__umtx_op(td, uap->obj, uap->op, uap->val, uap->uaddr1,
4911             uap->uaddr2, umtx_ops));
4912 }
4913
4914 #ifdef COMPAT_FREEBSD32
4915 #ifdef COMPAT_FREEBSD10
4916 int
4917 freebsd10_freebsd32_umtx_lock(struct thread *td,
4918     struct freebsd10_freebsd32_umtx_lock_args *uap)
4919 {
4920         return (do_lock_umtx32(td, (uint32_t *)uap->umtx, td->td_tid, NULL));
4921 }
4922
4923 int
4924 freebsd10_freebsd32_umtx_unlock(struct thread *td,
4925     struct freebsd10_freebsd32_umtx_unlock_args *uap)
4926 {
4927         return (do_unlock_umtx32(td, (uint32_t *)uap->umtx, td->td_tid));
4928 }
4929 #endif /* COMPAT_FREEBSD10 */
4930
4931 int
4932 freebsd32__umtx_op(struct thread *td, struct freebsd32__umtx_op_args *uap)
4933 {
4934
4935         return (kern__umtx_op(td, uap->obj, uap->op, uap->val, uap->uaddr,
4936             uap->uaddr2, &umtx_native_ops32));
4937 }
4938 #endif /* COMPAT_FREEBSD32 */
4939
4940 void
4941 umtx_thread_init(struct thread *td)
4942 {
4943
4944         td->td_umtxq = umtxq_alloc();
4945         td->td_umtxq->uq_thread = td;
4946 }
4947
4948 void
4949 umtx_thread_fini(struct thread *td)
4950 {
4951
4952         umtxq_free(td->td_umtxq);
4953 }
4954
4955 /*
4956  * It will be called when new thread is created, e.g fork().
4957  */
4958 void
4959 umtx_thread_alloc(struct thread *td)
4960 {
4961         struct umtx_q *uq;
4962
4963         uq = td->td_umtxq;
4964         uq->uq_inherited_pri = PRI_MAX;
4965
4966         KASSERT(uq->uq_flags == 0, ("uq_flags != 0"));
4967         KASSERT(uq->uq_thread == td, ("uq_thread != td"));
4968         KASSERT(uq->uq_pi_blocked == NULL, ("uq_pi_blocked != NULL"));
4969         KASSERT(TAILQ_EMPTY(&uq->uq_pi_contested), ("uq_pi_contested is not empty"));
4970 }
4971
4972 /*
4973  * exec() hook.
4974  *
4975  * Clear robust lists for all process' threads, not delaying the
4976  * cleanup to thread exit, since the relevant address space is
4977  * destroyed right now.
4978  */
4979 void
4980 umtx_exec(struct proc *p)
4981 {
4982         struct thread *td;
4983
4984         KASSERT(p == curproc, ("need curproc"));
4985         KASSERT((p->p_flag & P_HADTHREADS) == 0 ||
4986             (p->p_flag & P_STOPPED_SINGLE) != 0,
4987             ("curproc must be single-threaded"));
4988         /*
4989          * There is no need to lock the list as only this thread can be
4990          * running.
4991          */
4992         FOREACH_THREAD_IN_PROC(p, td) {
4993                 KASSERT(td == curthread ||
4994                     ((td->td_flags & TDF_BOUNDARY) != 0 && TD_IS_SUSPENDED(td)),
4995                     ("running thread %p %p", p, td));
4996                 umtx_thread_cleanup(td);
4997                 td->td_rb_list = td->td_rbp_list = td->td_rb_inact = 0;
4998         }
4999 }
5000
5001 /*
5002  * thread exit hook.
5003  */
5004 void
5005 umtx_thread_exit(struct thread *td)
5006 {
5007
5008         umtx_thread_cleanup(td);
5009 }
5010
5011 static int
5012 umtx_read_uptr(struct thread *td, uintptr_t ptr, uintptr_t *res, bool compat32)
5013 {
5014         u_long res1;
5015         uint32_t res32;
5016         int error;
5017
5018         if (compat32) {
5019                 error = fueword32((void *)ptr, &res32);
5020                 if (error == 0)
5021                         res1 = res32;
5022         } else {
5023                 error = fueword((void *)ptr, &res1);
5024         }
5025         if (error == 0)
5026                 *res = res1;
5027         else
5028                 error = EFAULT;
5029         return (error);
5030 }
5031
5032 static void
5033 umtx_read_rb_list(struct thread *td, struct umutex *m, uintptr_t *rb_list,
5034     bool compat32)
5035 {
5036         struct umutex32 m32;
5037
5038         if (compat32) {
5039                 memcpy(&m32, m, sizeof(m32));
5040                 *rb_list = m32.m_rb_lnk;
5041         } else {
5042                 *rb_list = m->m_rb_lnk;
5043         }
5044 }
5045
5046 static int
5047 umtx_handle_rb(struct thread *td, uintptr_t rbp, uintptr_t *rb_list, bool inact,
5048     bool compat32)
5049 {
5050         struct umutex m;
5051         int error;
5052
5053         KASSERT(td->td_proc == curproc, ("need current vmspace"));
5054         error = copyin((void *)rbp, &m, sizeof(m));
5055         if (error != 0)
5056                 return (error);
5057         if (rb_list != NULL)
5058                 umtx_read_rb_list(td, &m, rb_list, compat32);
5059         if ((m.m_flags & UMUTEX_ROBUST) == 0)
5060                 return (EINVAL);
5061         if ((m.m_owner & ~UMUTEX_CONTESTED) != td->td_tid)
5062                 /* inact is cleared after unlock, allow the inconsistency */
5063                 return (inact ? 0 : EINVAL);
5064         return (do_unlock_umutex(td, (struct umutex *)rbp, true));
5065 }
5066
5067 static void
5068 umtx_cleanup_rb_list(struct thread *td, uintptr_t rb_list, uintptr_t *rb_inact,
5069     const char *name, bool compat32)
5070 {
5071         int error, i;
5072         uintptr_t rbp;
5073         bool inact;
5074
5075         if (rb_list == 0)
5076                 return;
5077         error = umtx_read_uptr(td, rb_list, &rbp, compat32);
5078         for (i = 0; error == 0 && rbp != 0 && i < umtx_max_rb; i++) {
5079                 if (rbp == *rb_inact) {
5080                         inact = true;
5081                         *rb_inact = 0;
5082                 } else
5083                         inact = false;
5084                 error = umtx_handle_rb(td, rbp, &rbp, inact, compat32);
5085         }
5086         if (i == umtx_max_rb && umtx_verbose_rb) {
5087                 uprintf("comm %s pid %d: reached umtx %smax rb %d\n",
5088                     td->td_proc->p_comm, td->td_proc->p_pid, name, umtx_max_rb);
5089         }
5090         if (error != 0 && umtx_verbose_rb) {
5091                 uprintf("comm %s pid %d: handling %srb error %d\n",
5092                     td->td_proc->p_comm, td->td_proc->p_pid, name, error);
5093         }
5094 }
5095
5096 /*
5097  * Clean up umtx data.
5098  */
5099 static void
5100 umtx_thread_cleanup(struct thread *td)
5101 {
5102         struct umtx_q *uq;
5103         struct umtx_pi *pi;
5104         uintptr_t rb_inact;
5105         bool compat32;
5106
5107         /*
5108          * Disown pi mutexes.
5109          */
5110         uq = td->td_umtxq;
5111         if (uq != NULL) {
5112                 if (uq->uq_inherited_pri != PRI_MAX ||
5113                     !TAILQ_EMPTY(&uq->uq_pi_contested)) {
5114                         mtx_lock(&umtx_lock);
5115                         uq->uq_inherited_pri = PRI_MAX;
5116                         while ((pi = TAILQ_FIRST(&uq->uq_pi_contested)) != NULL) {
5117                                 pi->pi_owner = NULL;
5118                                 TAILQ_REMOVE(&uq->uq_pi_contested, pi, pi_link);
5119                         }
5120                         mtx_unlock(&umtx_lock);
5121                 }
5122                 sched_lend_user_prio_cond(td, PRI_MAX);
5123         }
5124
5125         compat32 = (td->td_pflags2 & TDP2_COMPAT32RB) != 0;
5126         td->td_pflags2 &= ~TDP2_COMPAT32RB;
5127
5128         if (td->td_rb_inact == 0 && td->td_rb_list == 0 && td->td_rbp_list == 0)
5129                 return;
5130
5131         /*
5132          * Handle terminated robust mutexes.  Must be done after
5133          * robust pi disown, otherwise unlock could see unowned
5134          * entries.
5135          */
5136         rb_inact = td->td_rb_inact;
5137         if (rb_inact != 0)
5138                 (void)umtx_read_uptr(td, rb_inact, &rb_inact, compat32);
5139         umtx_cleanup_rb_list(td, td->td_rb_list, &rb_inact, "", compat32);
5140         umtx_cleanup_rb_list(td, td->td_rbp_list, &rb_inact, "priv ", compat32);
5141         if (rb_inact != 0)
5142                 (void)umtx_handle_rb(td, rb_inact, NULL, true, compat32);
5143 }