kern_umtx.c revision 151692
1139804Simp/*- 2139013Sdavidxu * Copyright (c) 2004, David Xu <davidxu@freebsd.org> 3112904Sjeff * Copyright (c) 2002, Jeffrey Roberson <jeff@freebsd.org> 4112904Sjeff * All rights reserved. 5112904Sjeff * 6112904Sjeff * Redistribution and use in source and binary forms, with or without 7112904Sjeff * modification, are permitted provided that the following conditions 8112904Sjeff * are met: 9112904Sjeff * 1. Redistributions of source code must retain the above copyright 10112904Sjeff * notice unmodified, this list of conditions, and the following 11112904Sjeff * disclaimer. 12112904Sjeff * 2. Redistributions in binary form must reproduce the above copyright 13112904Sjeff * notice, this list of conditions and the following disclaimer in the 14112904Sjeff * documentation and/or other materials provided with the distribution. 15112904Sjeff * 16112904Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17112904Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18112904Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19112904Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20112904Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21112904Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22112904Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23112904Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24112904Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25112904Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26112904Sjeff */ 27112904Sjeff 28116182Sobrien#include <sys/cdefs.h> 29116182Sobrien__FBSDID("$FreeBSD: head/sys/kern/kern_umtx.c 151692 2005-10-26 06:55:46Z davidxu $"); 30116182Sobrien 31112904Sjeff#include <sys/param.h> 32112904Sjeff#include <sys/kernel.h> 33131431Smarcel#include <sys/limits.h> 34112904Sjeff#include <sys/lock.h> 35115765Sjeff#include <sys/malloc.h> 36112904Sjeff#include <sys/mutex.h> 37112904Sjeff#include <sys/proc.h> 38112904Sjeff#include <sys/sysent.h> 39112904Sjeff#include <sys/systm.h> 40112904Sjeff#include <sys/sysproto.h> 41139013Sdavidxu#include <sys/eventhandler.h> 42112904Sjeff#include <sys/thr.h> 43112904Sjeff#include <sys/umtx.h> 44112904Sjeff 45139013Sdavidxu#include <vm/vm.h> 46139013Sdavidxu#include <vm/vm_param.h> 47139013Sdavidxu#include <vm/pmap.h> 48139013Sdavidxu#include <vm/vm_map.h> 49139013Sdavidxu#include <vm/vm_object.h> 50139013Sdavidxu 51139013Sdavidxu#define UMTX_PRIVATE 0 52139013Sdavidxu#define UMTX_SHARED 1 53139013Sdavidxu 54139013Sdavidxu#define UMTX_STATIC_SHARED 55139013Sdavidxu 56139013Sdavidxustruct umtx_key { 57139013Sdavidxu int type; 58139013Sdavidxu union { 59139013Sdavidxu struct { 60139013Sdavidxu vm_object_t object; 61139013Sdavidxu long offset; 62139013Sdavidxu } shared; 63139013Sdavidxu struct { 64139013Sdavidxu struct umtx *umtx; 65139013Sdavidxu long pid; 66139013Sdavidxu } private; 67139013Sdavidxu struct { 68139013Sdavidxu void *ptr; 69139013Sdavidxu long word; 70139013Sdavidxu } both; 71139013Sdavidxu } info; 72139013Sdavidxu}; 73139013Sdavidxu 74115765Sjeffstruct umtx_q { 75115765Sjeff LIST_ENTRY(umtx_q) uq_next; /* Linked list for the hash. */ 76139013Sdavidxu struct umtx_key uq_key; /* Umtx key. */ 77139257Sdavidxu struct thread *uq_thread; /* The thread waits on. */ 78139013Sdavidxu LIST_ENTRY(umtx_q) uq_rqnext; /* Linked list for requeuing. */ 79139013Sdavidxu vm_offset_t uq_addr; /* Umtx's virtual address. */ 80115765Sjeff}; 81115765Sjeff 82115765SjeffLIST_HEAD(umtx_head, umtx_q); 83138224Sdavidxustruct umtxq_chain { 84139013Sdavidxu struct mtx uc_lock; /* Lock for this chain. */ 85139013Sdavidxu struct umtx_head uc_queue; /* List of sleep queues. */ 86139257Sdavidxu#define UCF_BUSY 0x01 87139257Sdavidxu#define UCF_WANT 0x02 88139257Sdavidxu int uc_flags; 89138224Sdavidxu}; 90115765Sjeff 91138224Sdavidxu#define GOLDEN_RATIO_PRIME 2654404609U 92138224Sdavidxu#define UMTX_CHAINS 128 93138224Sdavidxu#define UMTX_SHIFTS (__WORD_BIT - 7) 94115765Sjeff 95138224Sdavidxustatic struct umtxq_chain umtxq_chains[UMTX_CHAINS]; 96138224Sdavidxustatic MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory"); 97115310Sjeff 98139013Sdavidxustatic void umtxq_init_chains(void *); 99139013Sdavidxustatic int umtxq_hash(struct umtx_key *key); 100139013Sdavidxustatic struct mtx *umtxq_mtx(int chain); 101139013Sdavidxustatic void umtxq_lock(struct umtx_key *key); 102139013Sdavidxustatic void umtxq_unlock(struct umtx_key *key); 103139257Sdavidxustatic void umtxq_busy(struct umtx_key *key); 104139257Sdavidxustatic void umtxq_unbusy(struct umtx_key *key); 105139013Sdavidxustatic void umtxq_insert(struct umtx_q *uq); 106139013Sdavidxustatic void umtxq_remove(struct umtx_q *uq); 107139013Sdavidxustatic int umtxq_sleep(struct thread *td, struct umtx_key *key, 108139013Sdavidxu int prio, const char *wmesg, int timo); 109139257Sdavidxustatic int umtxq_count(struct umtx_key *key); 110139257Sdavidxustatic int umtxq_signal(struct umtx_key *key, int nr_wakeup); 111139013Sdavidxu#ifdef UMTX_DYNAMIC_SHARED 112139013Sdavidxustatic void fork_handler(void *arg, struct proc *p1, struct proc *p2, 113139013Sdavidxu int flags); 114139013Sdavidxu#endif 115139013Sdavidxustatic int umtx_key_match(const struct umtx_key *k1, const struct umtx_key *k2); 116139013Sdavidxustatic int umtx_key_get(struct thread *td, struct umtx *umtx, 117139013Sdavidxu struct umtx_key *key); 118139013Sdavidxustatic void umtx_key_release(struct umtx_key *key); 119115310Sjeff 120139013SdavidxuSYSINIT(umtx, SI_SUB_EVENTHANDLER+1, SI_ORDER_MIDDLE, umtxq_init_chains, NULL); 121138224Sdavidxu 122143149Sdavidxustruct umtx_q * 123143149Sdavidxuumtxq_alloc(void) 124143149Sdavidxu{ 125143149Sdavidxu return (malloc(sizeof(struct umtx_q), M_UMTX, M_WAITOK)); 126143149Sdavidxu} 127143149Sdavidxu 128143149Sdavidxuvoid 129143149Sdavidxuumtxq_free(struct umtx_q *uq) 130143149Sdavidxu{ 131143149Sdavidxu free(uq, M_UMTX); 132143149Sdavidxu} 133143149Sdavidxu 134138224Sdavidxustatic void 135139013Sdavidxuumtxq_init_chains(void *arg __unused) 136138224Sdavidxu{ 137138224Sdavidxu int i; 138138224Sdavidxu 139138224Sdavidxu for (i = 0; i < UMTX_CHAINS; ++i) { 140138224Sdavidxu mtx_init(&umtxq_chains[i].uc_lock, "umtxq_lock", NULL, 141138224Sdavidxu MTX_DEF | MTX_DUPOK); 142139013Sdavidxu LIST_INIT(&umtxq_chains[i].uc_queue); 143139257Sdavidxu umtxq_chains[i].uc_flags = 0; 144138224Sdavidxu } 145139013Sdavidxu#ifdef UMTX_DYNAMIC_SHARED 146139013Sdavidxu EVENTHANDLER_REGISTER(process_fork, fork_handler, 0, 10000); 147139013Sdavidxu#endif 148138224Sdavidxu} 149138224Sdavidxu 150138224Sdavidxustatic inline int 151139013Sdavidxuumtxq_hash(struct umtx_key *key) 152138224Sdavidxu{ 153139013Sdavidxu unsigned n = (uintptr_t)key->info.both.ptr + key->info.both.word; 154138224Sdavidxu return (((n * GOLDEN_RATIO_PRIME) >> UMTX_SHIFTS) % UMTX_CHAINS); 155138224Sdavidxu} 156138224Sdavidxu 157139013Sdavidxustatic inline int 158139013Sdavidxuumtx_key_match(const struct umtx_key *k1, const struct umtx_key *k2) 159139013Sdavidxu{ 160139013Sdavidxu return (k1->type == k2->type && 161139013Sdavidxu k1->info.both.ptr == k2->info.both.ptr && 162139013Sdavidxu k1->info.both.word == k2->info.both.word); 163139013Sdavidxu} 164139013Sdavidxu 165139013Sdavidxustatic inline struct mtx * 166139013Sdavidxuumtxq_mtx(int chain) 167139013Sdavidxu{ 168139013Sdavidxu return (&umtxq_chains[chain].uc_lock); 169139013Sdavidxu} 170139013Sdavidxu 171138224Sdavidxustatic inline void 172139257Sdavidxuumtxq_busy(struct umtx_key *key) 173139257Sdavidxu{ 174139257Sdavidxu int chain = umtxq_hash(key); 175139257Sdavidxu 176139257Sdavidxu mtx_assert(umtxq_mtx(chain), MA_OWNED); 177139257Sdavidxu while (umtxq_chains[chain].uc_flags & UCF_BUSY) { 178139257Sdavidxu umtxq_chains[chain].uc_flags |= UCF_WANT; 179139257Sdavidxu msleep(&umtxq_chains[chain], umtxq_mtx(chain), 180139257Sdavidxu curthread->td_priority, "umtxq_busy", 0); 181139257Sdavidxu } 182139257Sdavidxu umtxq_chains[chain].uc_flags |= UCF_BUSY; 183139257Sdavidxu} 184139257Sdavidxu 185139257Sdavidxustatic inline void 186139257Sdavidxuumtxq_unbusy(struct umtx_key *key) 187139257Sdavidxu{ 188139257Sdavidxu int chain = umtxq_hash(key); 189139257Sdavidxu 190139257Sdavidxu mtx_assert(umtxq_mtx(chain), MA_OWNED); 191139258Sdavidxu KASSERT(umtxq_chains[chain].uc_flags & UCF_BUSY, ("not busy")); 192139257Sdavidxu umtxq_chains[chain].uc_flags &= ~UCF_BUSY; 193139257Sdavidxu if (umtxq_chains[chain].uc_flags & UCF_WANT) { 194139257Sdavidxu umtxq_chains[chain].uc_flags &= ~UCF_WANT; 195139257Sdavidxu wakeup(&umtxq_chains[chain]); 196139257Sdavidxu } 197139257Sdavidxu} 198139257Sdavidxu 199139257Sdavidxustatic inline void 200139013Sdavidxuumtxq_lock(struct umtx_key *key) 201138224Sdavidxu{ 202139013Sdavidxu int chain = umtxq_hash(key); 203139013Sdavidxu mtx_lock(umtxq_mtx(chain)); 204138224Sdavidxu} 205138224Sdavidxu 206138225Sdavidxustatic inline void 207139013Sdavidxuumtxq_unlock(struct umtx_key *key) 208138224Sdavidxu{ 209139013Sdavidxu int chain = umtxq_hash(key); 210139013Sdavidxu mtx_unlock(umtxq_mtx(chain)); 211138224Sdavidxu} 212138224Sdavidxu 213139013Sdavidxu/* 214139013Sdavidxu * Insert a thread onto the umtx queue. 215139013Sdavidxu */ 216139013Sdavidxustatic inline void 217139013Sdavidxuumtxq_insert(struct umtx_q *uq) 218115765Sjeff{ 219115765Sjeff struct umtx_head *head; 220139013Sdavidxu int chain = umtxq_hash(&uq->uq_key); 221139013Sdavidxu 222139257Sdavidxu mtx_assert(umtxq_mtx(chain), MA_OWNED); 223139013Sdavidxu head = &umtxq_chains[chain].uc_queue; 224139013Sdavidxu LIST_INSERT_HEAD(head, uq, uq_next); 225139013Sdavidxu mtx_lock_spin(&sched_lock); 226139013Sdavidxu uq->uq_thread->td_flags |= TDF_UMTXQ; 227139013Sdavidxu mtx_unlock_spin(&sched_lock); 228139013Sdavidxu} 229139013Sdavidxu 230139013Sdavidxu/* 231139013Sdavidxu * Remove thread from the umtx queue. 232139013Sdavidxu */ 233139013Sdavidxustatic inline void 234139013Sdavidxuumtxq_remove(struct umtx_q *uq) 235139013Sdavidxu{ 236139257Sdavidxu mtx_assert(umtxq_mtx(umtxq_hash(&uq->uq_key)), MA_OWNED); 237139013Sdavidxu if (uq->uq_thread->td_flags & TDF_UMTXQ) { 238139013Sdavidxu LIST_REMOVE(uq, uq_next); 239139013Sdavidxu /* turning off TDF_UMTXQ should be the last thing. */ 240139013Sdavidxu mtx_lock_spin(&sched_lock); 241139013Sdavidxu uq->uq_thread->td_flags &= ~TDF_UMTXQ; 242139013Sdavidxu mtx_unlock_spin(&sched_lock); 243139013Sdavidxu } 244139013Sdavidxu} 245139013Sdavidxu 246139013Sdavidxustatic int 247139013Sdavidxuumtxq_count(struct umtx_key *key) 248139013Sdavidxu{ 249115765Sjeff struct umtx_q *uq; 250139013Sdavidxu struct umtx_head *head; 251139013Sdavidxu int chain, count = 0; 252115765Sjeff 253139013Sdavidxu chain = umtxq_hash(key); 254139257Sdavidxu mtx_assert(umtxq_mtx(chain), MA_OWNED); 255139013Sdavidxu head = &umtxq_chains[chain].uc_queue; 256115765Sjeff LIST_FOREACH(uq, head, uq_next) { 257139013Sdavidxu if (umtx_key_match(&uq->uq_key, key)) { 258139013Sdavidxu if (++count > 1) 259139013Sdavidxu break; 260139013Sdavidxu } 261115765Sjeff } 262139013Sdavidxu return (count); 263115765Sjeff} 264115765Sjeff 265139257Sdavidxustatic int 266139257Sdavidxuumtxq_signal(struct umtx_key *key, int n_wake) 267115765Sjeff{ 268139257Sdavidxu struct umtx_q *uq, *next; 269115765Sjeff struct umtx_head *head; 270139013Sdavidxu struct thread *blocked = NULL; 271139257Sdavidxu int chain, ret; 272115765Sjeff 273139257Sdavidxu ret = 0; 274139013Sdavidxu chain = umtxq_hash(key); 275139257Sdavidxu mtx_assert(umtxq_mtx(chain), MA_OWNED); 276139013Sdavidxu head = &umtxq_chains[chain].uc_queue; 277139257Sdavidxu for (uq = LIST_FIRST(head); uq; uq = next) { 278139013Sdavidxu next = LIST_NEXT(uq, uq_next); 279139013Sdavidxu if (umtx_key_match(&uq->uq_key, key)) { 280139013Sdavidxu blocked = uq->uq_thread; 281139013Sdavidxu umtxq_remove(uq); 282139013Sdavidxu wakeup(blocked); 283139257Sdavidxu if (++ret >= n_wake) 284139257Sdavidxu break; 285139013Sdavidxu } 286139013Sdavidxu } 287139257Sdavidxu return (ret); 288138224Sdavidxu} 289138224Sdavidxu 290138224Sdavidxustatic inline int 291139013Sdavidxuumtxq_sleep(struct thread *td, struct umtx_key *key, int priority, 292139013Sdavidxu const char *wmesg, int timo) 293138224Sdavidxu{ 294139013Sdavidxu int chain = umtxq_hash(key); 295139751Sdavidxu int error = msleep(td, umtxq_mtx(chain), priority, wmesg, timo); 296139751Sdavidxu if (error == EWOULDBLOCK) 297139751Sdavidxu error = ETIMEDOUT; 298139751Sdavidxu return (error); 299138224Sdavidxu} 300138224Sdavidxu 301139013Sdavidxustatic int 302139013Sdavidxuumtx_key_get(struct thread *td, struct umtx *umtx, struct umtx_key *key) 303139013Sdavidxu{ 304139013Sdavidxu#if defined(UMTX_DYNAMIC_SHARED) || defined(UMTX_STATIC_SHARED) 305139013Sdavidxu vm_map_t map; 306139013Sdavidxu vm_map_entry_t entry; 307139013Sdavidxu vm_pindex_t pindex; 308139013Sdavidxu vm_prot_t prot; 309139013Sdavidxu boolean_t wired; 310139013Sdavidxu 311139013Sdavidxu map = &td->td_proc->p_vmspace->vm_map; 312139013Sdavidxu if (vm_map_lookup(&map, (vm_offset_t)umtx, VM_PROT_WRITE, 313139013Sdavidxu &entry, &key->info.shared.object, &pindex, &prot, 314139013Sdavidxu &wired) != KERN_SUCCESS) { 315139013Sdavidxu return EFAULT; 316139013Sdavidxu } 317139013Sdavidxu#endif 318139013Sdavidxu 319139013Sdavidxu#if defined(UMTX_DYNAMIC_SHARED) 320139013Sdavidxu key->type = UMTX_SHARED; 321139013Sdavidxu key->info.shared.offset = entry->offset + entry->start - 322139013Sdavidxu (vm_offset_t)umtx; 323139013Sdavidxu /* 324139013Sdavidxu * Add object reference, if we don't do this, a buggy application 325139013Sdavidxu * deallocates the object, the object will be reused by other 326139013Sdavidxu * applications, then unlock will wake wrong thread. 327139013Sdavidxu */ 328139013Sdavidxu vm_object_reference(key->info.shared.object); 329139013Sdavidxu vm_map_lookup_done(map, entry); 330139013Sdavidxu#elif defined(UMTX_STATIC_SHARED) 331139013Sdavidxu if (VM_INHERIT_SHARE == entry->inheritance) { 332139013Sdavidxu key->type = UMTX_SHARED; 333139013Sdavidxu key->info.shared.offset = entry->offset + entry->start - 334139013Sdavidxu (vm_offset_t)umtx; 335139013Sdavidxu vm_object_reference(key->info.shared.object); 336139013Sdavidxu } else { 337139013Sdavidxu key->type = UMTX_PRIVATE; 338139013Sdavidxu key->info.private.umtx = umtx; 339139013Sdavidxu key->info.private.pid = td->td_proc->p_pid; 340139013Sdavidxu } 341139013Sdavidxu vm_map_lookup_done(map, entry); 342139013Sdavidxu#else 343139013Sdavidxu key->type = UMTX_PRIVATE; 344139013Sdavidxu key->info.private.umtx = umtx; 345139013Sdavidxu key->info.private.pid = td->td_proc->p_pid; 346139013Sdavidxu#endif 347139013Sdavidxu return (0); 348139013Sdavidxu} 349139013Sdavidxu 350139013Sdavidxustatic inline void 351139013Sdavidxuumtx_key_release(struct umtx_key *key) 352139013Sdavidxu{ 353139013Sdavidxu if (key->type == UMTX_SHARED) 354139013Sdavidxu vm_object_deallocate(key->info.shared.object); 355139013Sdavidxu} 356139013Sdavidxu 357138224Sdavidxustatic inline int 358139013Sdavidxuumtxq_queue_me(struct thread *td, struct umtx *umtx, struct umtx_q *uq) 359138224Sdavidxu{ 360139013Sdavidxu int error; 361138224Sdavidxu 362139013Sdavidxu if ((error = umtx_key_get(td, umtx, &uq->uq_key)) != 0) 363139013Sdavidxu return (error); 364139013Sdavidxu 365139013Sdavidxu uq->uq_addr = (vm_offset_t)umtx; 366139013Sdavidxu uq->uq_thread = td; 367139013Sdavidxu umtxq_lock(&uq->uq_key); 368139257Sdavidxu /* hmm, for condition variable, we don't need busy flag. */ 369139257Sdavidxu umtxq_busy(&uq->uq_key); 370139013Sdavidxu umtxq_insert(uq); 371139257Sdavidxu umtxq_unbusy(&uq->uq_key); 372139013Sdavidxu umtxq_unlock(&uq->uq_key); 373139013Sdavidxu return (0); 374138224Sdavidxu} 375138224Sdavidxu 376139013Sdavidxu#if defined(UMTX_DYNAMIC_SHARED) 377138224Sdavidxustatic void 378139013Sdavidxufork_handler(void *arg, struct proc *p1, struct proc *p2, int flags) 379138224Sdavidxu{ 380139013Sdavidxu vm_map_t map; 381139013Sdavidxu vm_map_entry_t entry; 382139013Sdavidxu vm_object_t object; 383139013Sdavidxu vm_pindex_t pindex; 384139013Sdavidxu vm_prot_t prot; 385139013Sdavidxu boolean_t wired; 386139013Sdavidxu struct umtx_key key; 387139013Sdavidxu LIST_HEAD(, umtx_q) workq; 388138224Sdavidxu struct umtx_q *uq; 389139013Sdavidxu struct thread *td; 390139013Sdavidxu int onq; 391138224Sdavidxu 392139013Sdavidxu LIST_INIT(&workq); 393139013Sdavidxu 394139013Sdavidxu /* Collect threads waiting on umtxq */ 395139013Sdavidxu PROC_LOCK(p1); 396139013Sdavidxu FOREACH_THREAD_IN_PROC(p1, td) { 397139013Sdavidxu if (td->td_flags & TDF_UMTXQ) { 398139013Sdavidxu uq = td->td_umtxq; 399139013Sdavidxu if (uq) 400139013Sdavidxu LIST_INSERT_HEAD(&workq, uq, uq_rqnext); 401138224Sdavidxu } 402115765Sjeff } 403139013Sdavidxu PROC_UNLOCK(p1); 404139013Sdavidxu 405139013Sdavidxu LIST_FOREACH(uq, &workq, uq_rqnext) { 406139013Sdavidxu map = &p1->p_vmspace->vm_map; 407139013Sdavidxu if (vm_map_lookup(&map, uq->uq_addr, VM_PROT_WRITE, 408139013Sdavidxu &entry, &object, &pindex, &prot, &wired) != KERN_SUCCESS) { 409139013Sdavidxu continue; 410139013Sdavidxu } 411139013Sdavidxu key.type = UMTX_SHARED; 412139013Sdavidxu key.info.shared.object = object; 413139013Sdavidxu key.info.shared.offset = entry->offset + entry->start - 414139013Sdavidxu uq->uq_addr; 415139013Sdavidxu if (umtx_key_match(&key, &uq->uq_key)) { 416139013Sdavidxu vm_map_lookup_done(map, entry); 417139013Sdavidxu continue; 418139013Sdavidxu } 419139013Sdavidxu 420139013Sdavidxu umtxq_lock(&uq->uq_key); 421139257Sdavidxu umtxq_busy(&uq->uq_key); 422139013Sdavidxu if (uq->uq_thread->td_flags & TDF_UMTXQ) { 423139013Sdavidxu umtxq_remove(uq); 424139013Sdavidxu onq = 1; 425139013Sdavidxu } else 426139013Sdavidxu onq = 0; 427139257Sdavidxu umtxq_unbusy(&uq->uq_key); 428139013Sdavidxu umtxq_unlock(&uq->uq_key); 429139013Sdavidxu if (onq) { 430139013Sdavidxu vm_object_deallocate(uq->uq_key.info.shared.object); 431139013Sdavidxu uq->uq_key = key; 432139013Sdavidxu umtxq_lock(&uq->uq_key); 433139257Sdavidxu umtxq_busy(&uq->uq_key); 434139013Sdavidxu umtxq_insert(uq); 435139257Sdavidxu umtxq_unbusy(&uq->uq_key); 436139013Sdavidxu umtxq_unlock(&uq->uq_key); 437139013Sdavidxu vm_object_reference(uq->uq_key.info.shared.object); 438139013Sdavidxu } 439139013Sdavidxu vm_map_lookup_done(map, entry); 440139013Sdavidxu } 441115765Sjeff} 442139013Sdavidxu#endif 443115765Sjeff 444139013Sdavidxustatic int 445139013Sdavidxu_do_lock(struct thread *td, struct umtx *umtx, long id, int timo) 446112904Sjeff{ 447143149Sdavidxu struct umtx_q *uq; 448112904Sjeff intptr_t owner; 449112967Sjake intptr_t old; 450138224Sdavidxu int error = 0; 451112904Sjeff 452143149Sdavidxu uq = td->td_umtxq; 453112904Sjeff /* 454139013Sdavidxu * Care must be exercised when dealing with umtx structure. It 455112904Sjeff * can fault on any access. 456112904Sjeff */ 457112904Sjeff 458112904Sjeff for (;;) { 459112904Sjeff /* 460112904Sjeff * Try the uncontested case. This should be done in userland. 461112904Sjeff */ 462112904Sjeff owner = casuptr((intptr_t *)&umtx->u_owner, 463139013Sdavidxu UMTX_UNOWNED, id); 464112904Sjeff 465138224Sdavidxu /* The acquire succeeded. */ 466138224Sdavidxu if (owner == UMTX_UNOWNED) 467138224Sdavidxu return (0); 468138224Sdavidxu 469115765Sjeff /* The address was invalid. */ 470115765Sjeff if (owner == -1) 471115765Sjeff return (EFAULT); 472115765Sjeff 473115765Sjeff /* If no one owns it but it is contested try to acquire it. */ 474115765Sjeff if (owner == UMTX_CONTESTED) { 475115765Sjeff owner = casuptr((intptr_t *)&umtx->u_owner, 476139013Sdavidxu UMTX_CONTESTED, id | UMTX_CONTESTED); 477115765Sjeff 478138224Sdavidxu if (owner == UMTX_CONTESTED) 479138224Sdavidxu return (0); 480138224Sdavidxu 481115765Sjeff /* The address was invalid. */ 482115765Sjeff if (owner == -1) 483115765Sjeff return (EFAULT); 484115765Sjeff 485115765Sjeff /* If this failed the lock has changed, restart. */ 486115765Sjeff continue; 487112904Sjeff } 488112904Sjeff 489138224Sdavidxu /* 490138224Sdavidxu * If we caught a signal, we have retried and now 491138224Sdavidxu * exit immediately. 492138224Sdavidxu */ 493143149Sdavidxu if (error || (error = umtxq_queue_me(td, umtx, uq)) != 0) 494138224Sdavidxu return (error); 495112904Sjeff 496112904Sjeff /* 497112904Sjeff * Set the contested bit so that a release in user space 498112904Sjeff * knows to use the system call for unlock. If this fails 499112904Sjeff * either some one else has acquired the lock or it has been 500112904Sjeff * released. 501112904Sjeff */ 502112967Sjake old = casuptr((intptr_t *)&umtx->u_owner, owner, 503112967Sjake owner | UMTX_CONTESTED); 504112904Sjeff 505112904Sjeff /* The address was invalid. */ 506112967Sjake if (old == -1) { 507143149Sdavidxu umtxq_lock(&uq->uq_key); 508143149Sdavidxu umtxq_busy(&uq->uq_key); 509143149Sdavidxu umtxq_remove(uq); 510143149Sdavidxu umtxq_unbusy(&uq->uq_key); 511143149Sdavidxu umtxq_unlock(&uq->uq_key); 512143149Sdavidxu umtx_key_release(&uq->uq_key); 513115765Sjeff return (EFAULT); 514112904Sjeff } 515112904Sjeff 516112904Sjeff /* 517115765Sjeff * We set the contested bit, sleep. Otherwise the lock changed 518117685Smtm * and we need to retry or we lost a race to the thread 519117685Smtm * unlocking the umtx. 520112904Sjeff */ 521143149Sdavidxu umtxq_lock(&uq->uq_key); 522139013Sdavidxu if (old == owner && (td->td_flags & TDF_UMTXQ)) { 523143149Sdavidxu error = umtxq_sleep(td, &uq->uq_key, 524139257Sdavidxu td->td_priority | PCATCH, 525139013Sdavidxu "umtx", timo); 526138224Sdavidxu } 527143149Sdavidxu umtxq_busy(&uq->uq_key); 528143149Sdavidxu umtxq_remove(uq); 529143149Sdavidxu umtxq_unbusy(&uq->uq_key); 530143149Sdavidxu umtxq_unlock(&uq->uq_key); 531143149Sdavidxu umtx_key_release(&uq->uq_key); 532112904Sjeff } 533117743Smtm 534117743Smtm return (0); 535112904Sjeff} 536112904Sjeff 537139013Sdavidxustatic int 538139013Sdavidxudo_lock(struct thread *td, struct umtx *umtx, long id, 539140245Sdavidxu struct timespec *timeout) 540112904Sjeff{ 541140245Sdavidxu struct timespec ts, ts2, ts3; 542139013Sdavidxu struct timeval tv; 543140245Sdavidxu int error; 544139013Sdavidxu 545140245Sdavidxu if (timeout == NULL) { 546139013Sdavidxu error = _do_lock(td, umtx, id, 0); 547139013Sdavidxu } else { 548140245Sdavidxu getnanouptime(&ts); 549140245Sdavidxu timespecadd(&ts, timeout); 550140245Sdavidxu TIMESPEC_TO_TIMEVAL(&tv, timeout); 551139013Sdavidxu for (;;) { 552140245Sdavidxu error = _do_lock(td, umtx, id, tvtohz(&tv)); 553140245Sdavidxu if (error != ETIMEDOUT) 554140245Sdavidxu break; 555140245Sdavidxu getnanouptime(&ts2); 556140245Sdavidxu if (timespeccmp(&ts2, &ts, >=)) { 557139751Sdavidxu error = ETIMEDOUT; 558139013Sdavidxu break; 559139013Sdavidxu } 560140245Sdavidxu ts3 = ts; 561140245Sdavidxu timespecsub(&ts3, &ts2); 562140245Sdavidxu TIMESPEC_TO_TIMEVAL(&tv, &ts3); 563139013Sdavidxu } 564139013Sdavidxu } 565139258Sdavidxu /* 566139258Sdavidxu * This lets userland back off critical region if needed. 567139258Sdavidxu */ 568139258Sdavidxu if (error == ERESTART) 569139258Sdavidxu error = EINTR; 570139013Sdavidxu return (error); 571139013Sdavidxu} 572139013Sdavidxu 573139013Sdavidxustatic int 574139013Sdavidxudo_unlock(struct thread *td, struct umtx *umtx, long id) 575139013Sdavidxu{ 576139013Sdavidxu struct umtx_key key; 577112904Sjeff intptr_t owner; 578112967Sjake intptr_t old; 579139257Sdavidxu int error; 580139257Sdavidxu int count; 581112904Sjeff 582112904Sjeff /* 583112904Sjeff * Make sure we own this mtx. 584112904Sjeff * 585112904Sjeff * XXX Need a {fu,su}ptr this is not correct on arch where 586112904Sjeff * sizeof(intptr_t) != sizeof(long). 587112904Sjeff */ 588115765Sjeff if ((owner = fuword(&umtx->u_owner)) == -1) 589115765Sjeff return (EFAULT); 590115765Sjeff 591139013Sdavidxu if ((owner & ~UMTX_CONTESTED) != id) 592115765Sjeff return (EPERM); 593112904Sjeff 594117685Smtm /* We should only ever be in here for contested locks */ 595119836Stjr if ((owner & UMTX_CONTESTED) == 0) 596119836Stjr return (EINVAL); 597112904Sjeff 598139257Sdavidxu if ((error = umtx_key_get(td, umtx, &key)) != 0) 599139257Sdavidxu return (error); 600139257Sdavidxu 601139257Sdavidxu umtxq_lock(&key); 602139257Sdavidxu umtxq_busy(&key); 603139257Sdavidxu count = umtxq_count(&key); 604139257Sdavidxu umtxq_unlock(&key); 605139257Sdavidxu 606117743Smtm /* 607117743Smtm * When unlocking the umtx, it must be marked as unowned if 608117743Smtm * there is zero or one thread only waiting for it. 609117743Smtm * Otherwise, it must be marked as contested. 610117743Smtm */ 611139257Sdavidxu old = casuptr((intptr_t *)&umtx->u_owner, owner, 612139257Sdavidxu count <= 1 ? UMTX_UNOWNED : UMTX_CONTESTED); 613139257Sdavidxu umtxq_lock(&key); 614139257Sdavidxu umtxq_signal(&key, 0); 615139257Sdavidxu umtxq_unbusy(&key); 616139257Sdavidxu umtxq_unlock(&key); 617139257Sdavidxu umtx_key_release(&key); 618115765Sjeff if (old == -1) 619115765Sjeff return (EFAULT); 620138224Sdavidxu if (old != owner) 621138224Sdavidxu return (EINVAL); 622115765Sjeff return (0); 623112904Sjeff} 624139013Sdavidxu 625139013Sdavidxustatic int 626140245Sdavidxudo_wait(struct thread *td, struct umtx *umtx, long id, struct timespec *timeout) 627139013Sdavidxu{ 628143149Sdavidxu struct umtx_q *uq; 629140245Sdavidxu struct timespec ts, ts2, ts3; 630139013Sdavidxu struct timeval tv; 631139427Sdavidxu long tmp; 632140245Sdavidxu int error = 0; 633139013Sdavidxu 634143149Sdavidxu uq = td->td_umtxq; 635143149Sdavidxu if ((error = umtxq_queue_me(td, umtx, uq)) != 0) 636139013Sdavidxu return (error); 637139427Sdavidxu tmp = fuword(&umtx->u_owner); 638139427Sdavidxu if (tmp != id) { 639143149Sdavidxu umtxq_lock(&uq->uq_key); 640143149Sdavidxu umtxq_remove(uq); 641143149Sdavidxu umtxq_unlock(&uq->uq_key); 642140245Sdavidxu } else if (timeout == NULL) { 643143149Sdavidxu umtxq_lock(&uq->uq_key); 644139013Sdavidxu if (td->td_flags & TDF_UMTXQ) 645143149Sdavidxu error = umtxq_sleep(td, &uq->uq_key, 646139013Sdavidxu td->td_priority | PCATCH, "ucond", 0); 647139257Sdavidxu if (!(td->td_flags & TDF_UMTXQ)) 648139257Sdavidxu error = 0; 649139257Sdavidxu else 650143149Sdavidxu umtxq_remove(uq); 651143149Sdavidxu umtxq_unlock(&uq->uq_key); 652139013Sdavidxu } else { 653140245Sdavidxu getnanouptime(&ts); 654140245Sdavidxu timespecadd(&ts, timeout); 655140245Sdavidxu TIMESPEC_TO_TIMEVAL(&tv, timeout); 656139013Sdavidxu for (;;) { 657143149Sdavidxu umtxq_lock(&uq->uq_key); 658140245Sdavidxu if (td->td_flags & TDF_UMTXQ) { 659143149Sdavidxu error = umtxq_sleep(td, &uq->uq_key, 660140245Sdavidxu td->td_priority | PCATCH, 661140245Sdavidxu "ucond", tvtohz(&tv)); 662140245Sdavidxu } 663140245Sdavidxu if (!(td->td_flags & TDF_UMTXQ)) { 664143149Sdavidxu umtxq_unlock(&uq->uq_key); 665140245Sdavidxu goto out; 666140245Sdavidxu } 667143149Sdavidxu umtxq_unlock(&uq->uq_key); 668140245Sdavidxu if (error != ETIMEDOUT) 669140245Sdavidxu break; 670140245Sdavidxu getnanouptime(&ts2); 671140245Sdavidxu if (timespeccmp(&ts2, &ts, >=)) { 672139751Sdavidxu error = ETIMEDOUT; 673139013Sdavidxu break; 674139013Sdavidxu } 675140245Sdavidxu ts3 = ts; 676140245Sdavidxu timespecsub(&ts3, &ts2); 677140245Sdavidxu TIMESPEC_TO_TIMEVAL(&tv, &ts3); 678139013Sdavidxu } 679143149Sdavidxu umtxq_lock(&uq->uq_key); 680143149Sdavidxu umtxq_remove(uq); 681143149Sdavidxu umtxq_unlock(&uq->uq_key); 682139013Sdavidxu } 683140245Sdavidxuout: 684143149Sdavidxu umtx_key_release(&uq->uq_key); 685139257Sdavidxu if (error == ERESTART) 686139257Sdavidxu error = EINTR; 687139013Sdavidxu return (error); 688139013Sdavidxu} 689139013Sdavidxu 690151692Sdavidxuint 691151692Sdavidxukern_umtx_wake(struct thread *td, void *uaddr, int n_wake) 692139013Sdavidxu{ 693139013Sdavidxu struct umtx_key key; 694139257Sdavidxu int ret; 695139013Sdavidxu 696139257Sdavidxu if ((ret = umtx_key_get(td, uaddr, &key)) != 0) 697139257Sdavidxu return (ret); 698139258Sdavidxu umtxq_lock(&key); 699139257Sdavidxu ret = umtxq_signal(&key, n_wake); 700139258Sdavidxu umtxq_unlock(&key); 701139257Sdavidxu umtx_key_release(&key); 702139013Sdavidxu return (0); 703139013Sdavidxu} 704139013Sdavidxu 705139013Sdavidxuint 706139013Sdavidxu_umtx_lock(struct thread *td, struct _umtx_lock_args *uap) 707139013Sdavidxu /* struct umtx *umtx */ 708139013Sdavidxu{ 709139013Sdavidxu return _do_lock(td, uap->umtx, td->td_tid, 0); 710139013Sdavidxu} 711139013Sdavidxu 712139013Sdavidxuint 713139013Sdavidxu_umtx_unlock(struct thread *td, struct _umtx_unlock_args *uap) 714139013Sdavidxu /* struct umtx *umtx */ 715139013Sdavidxu{ 716139013Sdavidxu return do_unlock(td, uap->umtx, td->td_tid); 717139013Sdavidxu} 718139013Sdavidxu 719139013Sdavidxuint 720139013Sdavidxu_umtx_op(struct thread *td, struct _umtx_op_args *uap) 721139013Sdavidxu{ 722140245Sdavidxu struct timespec timeout; 723139013Sdavidxu struct timespec *ts; 724139013Sdavidxu int error; 725139013Sdavidxu 726139013Sdavidxu switch(uap->op) { 727139013Sdavidxu case UMTX_OP_LOCK: 728139013Sdavidxu /* Allow a null timespec (wait forever). */ 729139292Sdavidxu if (uap->uaddr2 == NULL) 730139013Sdavidxu ts = NULL; 731139013Sdavidxu else { 732140245Sdavidxu error = copyin(uap->uaddr2, &timeout, sizeof(timeout)); 733139013Sdavidxu if (error != 0) 734140102Sdavidxu break; 735140245Sdavidxu if (timeout.tv_nsec >= 1000000000 || 736140245Sdavidxu timeout.tv_nsec < 0) { 737140102Sdavidxu error = EINVAL; 738140102Sdavidxu break; 739140102Sdavidxu } 740140245Sdavidxu ts = &timeout; 741139013Sdavidxu } 742140102Sdavidxu error = do_lock(td, uap->umtx, uap->id, ts); 743140102Sdavidxu break; 744139013Sdavidxu case UMTX_OP_UNLOCK: 745140102Sdavidxu error = do_unlock(td, uap->umtx, uap->id); 746140102Sdavidxu break; 747139427Sdavidxu case UMTX_OP_WAIT: 748139013Sdavidxu /* Allow a null timespec (wait forever). */ 749139292Sdavidxu if (uap->uaddr2 == NULL) 750139013Sdavidxu ts = NULL; 751139013Sdavidxu else { 752140245Sdavidxu error = copyin(uap->uaddr2, &timeout, sizeof(timeout)); 753139013Sdavidxu if (error != 0) 754140102Sdavidxu break; 755140245Sdavidxu if (timeout.tv_nsec >= 1000000000 || 756140245Sdavidxu timeout.tv_nsec < 0) { 757140102Sdavidxu error = EINVAL; 758140102Sdavidxu break; 759140102Sdavidxu } 760140245Sdavidxu ts = &timeout; 761139013Sdavidxu } 762140102Sdavidxu error = do_wait(td, uap->umtx, uap->id, ts); 763140102Sdavidxu break; 764139013Sdavidxu case UMTX_OP_WAKE: 765151692Sdavidxu error = kern_umtx_wake(td, uap->umtx, uap->id); 766140102Sdavidxu break; 767139013Sdavidxu default: 768140102Sdavidxu error = EINVAL; 769140102Sdavidxu break; 770139013Sdavidxu } 771140421Sdavidxu return (error); 772139013Sdavidxu} 773