kern_umtx.c revision 115765
1112904Sjeff/* 2112904Sjeff * Copyright (c) 2002, Jeffrey Roberson <jeff@freebsd.org> 3112904Sjeff * All rights reserved. 4112904Sjeff * 5112904Sjeff * Redistribution and use in source and binary forms, with or without 6112904Sjeff * modification, are permitted provided that the following conditions 7112904Sjeff * are met: 8112904Sjeff * 1. Redistributions of source code must retain the above copyright 9112904Sjeff * notice unmodified, this list of conditions, and the following 10112904Sjeff * disclaimer. 11112904Sjeff * 2. Redistributions in binary form must reproduce the above copyright 12112904Sjeff * notice, this list of conditions and the following disclaimer in the 13112904Sjeff * documentation and/or other materials provided with the distribution. 14112904Sjeff * 15112904Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16112904Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17112904Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18112904Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19112904Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20112904Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21112904Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22112904Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23112904Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24112904Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25112904Sjeff * 26112904Sjeff * $FreeBSD: head/sys/kern/kern_umtx.c 115765 2003-06-03 05:24:46Z jeff $ 27112904Sjeff * 28112904Sjeff */ 29112904Sjeff 30112904Sjeff#include <sys/param.h> 31112904Sjeff#include <sys/kernel.h> 32112904Sjeff#include <sys/lock.h> 33115765Sjeff#include <sys/malloc.h> 34112904Sjeff#include <sys/mutex.h> 35112904Sjeff#include <sys/proc.h> 36112904Sjeff#include <sys/signalvar.h> 37112904Sjeff#include <sys/sysent.h> 38112904Sjeff#include <sys/systm.h> 39112904Sjeff#include <sys/sysproto.h> 40115765Sjeff#include <sys/sx.h> 41112904Sjeff#include <sys/thr.h> 42112904Sjeff#include <sys/umtx.h> 43112904Sjeff 44115765Sjeffstruct umtx_q { 45115765Sjeff LIST_ENTRY(umtx_q) uq_next; /* Linked list for the hash. */ 46115765Sjeff TAILQ_HEAD(, thread) uq_tdq; /* List of threads blocked here. */ 47115765Sjeff struct umtx *uq_umtx; /* Pointer key component. */ 48115765Sjeff pid_t uq_pid; /* Pid key component. */ 49115765Sjeff}; 50115765Sjeff 51115765Sjeff#define UMTX_QUEUES 128 52115765Sjeff#define UMTX_HASH(pid, umtx) \ 53115765Sjeff (((uintptr_t)pid + ((uintptr_t)umtx & ~65535)) % UMTX_QUEUES) 54115765Sjeff 55115765SjeffLIST_HEAD(umtx_head, umtx_q); 56115765Sjeffstatic struct umtx_head queues[UMTX_QUEUES]; 57115765Sjeffstatic MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory"); 58115765Sjeff 59115765Sjeffstatic struct mtx umtx_lock; 60115765SjeffMTX_SYSINIT(umtx, &umtx_lock, "umtx", MTX_DEF); 61115765Sjeff 62115310Sjeff#define UMTX_LOCK() mtx_lock(&umtx_lock); 63115310Sjeff#define UMTX_UNLOCK() mtx_unlock(&umtx_lock); 64115310Sjeff 65115310Sjeff 66115765Sjeffstatic struct umtx_q *umtx_lookup(struct thread *, struct umtx *umtx); 67115765Sjeffstatic struct umtx_q *umtx_insert(struct thread *, struct umtx *umtx); 68115310Sjeff 69115765Sjeffstatic struct umtx_q * 70115765Sjeffumtx_lookup(struct thread *td, struct umtx *umtx) 71115765Sjeff{ 72115765Sjeff struct umtx_head *head; 73115765Sjeff struct umtx_q *uq; 74115765Sjeff pid_t pid; 75115765Sjeff 76115765Sjeff pid = td->td_proc->p_pid; 77115765Sjeff 78115765Sjeff head = &queues[UMTX_HASH(td->td_proc->p_pid, umtx)]; 79115765Sjeff 80115765Sjeff LIST_FOREACH(uq, head, uq_next) { 81115765Sjeff if (uq->uq_pid == pid && uq->uq_umtx == umtx) 82115765Sjeff return (uq); 83115765Sjeff } 84115765Sjeff 85115765Sjeff return (NULL); 86115765Sjeff} 87115765Sjeff 88115765Sjeff/* 89115765Sjeff * Insert a thread onto the umtx queue. 90115765Sjeff */ 91115765Sjeffstatic struct umtx_q * 92115765Sjeffumtx_insert(struct thread *td, struct umtx *umtx) 93115765Sjeff{ 94115765Sjeff struct umtx_head *head; 95115765Sjeff struct umtx_q *uq; 96115765Sjeff pid_t pid; 97115765Sjeff 98115765Sjeff pid = td->td_proc->p_pid; 99115765Sjeff 100115765Sjeff if ((uq = umtx_lookup(td, umtx)) == NULL) { 101115765Sjeff struct umtx_q *ins; 102115765Sjeff 103115765Sjeff UMTX_UNLOCK(); 104115765Sjeff ins = malloc(sizeof(*uq), M_UMTX, M_ZERO | M_WAITOK); 105115765Sjeff UMTX_LOCK(); 106115765Sjeff 107115765Sjeff /* 108115765Sjeff * Some one else could have succeeded while we were blocked 109115765Sjeff * waiting on memory. 110115765Sjeff */ 111115765Sjeff if ((uq = umtx_lookup(td, umtx)) == NULL) { 112115765Sjeff head = &queues[UMTX_HASH(pid, umtx)]; 113115765Sjeff uq = ins; 114115765Sjeff uq->uq_pid = pid; 115115765Sjeff uq->uq_umtx = umtx; 116115765Sjeff LIST_INSERT_HEAD(head, uq, uq_next); 117115765Sjeff TAILQ_INIT(&uq->uq_tdq); 118115765Sjeff } else 119115765Sjeff free(ins, M_UMTX); 120115765Sjeff } 121115765Sjeff 122115765Sjeff /* 123115765Sjeff * Insert us onto the end of the TAILQ. 124115765Sjeff */ 125115765Sjeff TAILQ_INSERT_TAIL(&uq->uq_tdq, td, td_umtx); 126115765Sjeff 127115765Sjeff return (uq); 128115765Sjeff} 129115765Sjeff 130115765Sjeffstatic void 131115765Sjeffumtx_remove(struct umtx_q *uq, struct thread *td) 132115765Sjeff{ 133115765Sjeff TAILQ_REMOVE(&uq->uq_tdq, td, td_umtx); 134115765Sjeff 135115765Sjeff if (TAILQ_EMPTY(&uq->uq_tdq)) { 136115765Sjeff LIST_REMOVE(uq, uq_next); 137115765Sjeff free(uq, M_UMTX); 138115765Sjeff } 139115765Sjeff} 140115765Sjeff 141112904Sjeffint 142112904Sjeff_umtx_lock(struct thread *td, struct _umtx_lock_args *uap) 143112904Sjeff /* struct umtx *umtx */ 144112904Sjeff{ 145115765Sjeff struct umtx_q *uq; 146112904Sjeff struct umtx *umtx; 147112904Sjeff intptr_t owner; 148112967Sjake intptr_t old; 149112904Sjeff int error; 150112904Sjeff 151115765Sjeff uq = NULL; 152112904Sjeff 153112904Sjeff /* 154112904Sjeff * Care must be exercised when dealing with this structure. It 155112904Sjeff * can fault on any access. 156112904Sjeff */ 157112904Sjeff umtx = uap->umtx; 158112904Sjeff 159112904Sjeff for (;;) { 160112904Sjeff /* 161112904Sjeff * Try the uncontested case. This should be done in userland. 162112904Sjeff */ 163112904Sjeff owner = casuptr((intptr_t *)&umtx->u_owner, 164112904Sjeff UMTX_UNOWNED, (intptr_t)td); 165112904Sjeff 166115765Sjeff /* The address was invalid. */ 167115765Sjeff if (owner == -1) 168115765Sjeff return (EFAULT); 169115765Sjeff 170112904Sjeff /* The acquire succeeded. */ 171115765Sjeff if (owner == UMTX_UNOWNED) 172115765Sjeff return (0); 173112904Sjeff 174115765Sjeff /* If no one owns it but it is contested try to acquire it. */ 175115765Sjeff if (owner == UMTX_CONTESTED) { 176115765Sjeff owner = casuptr((intptr_t *)&umtx->u_owner, 177115765Sjeff UMTX_CONTESTED, ((intptr_t)td | UMTX_CONTESTED)); 178115765Sjeff 179115765Sjeff /* The address was invalid. */ 180115765Sjeff if (owner == -1) 181115765Sjeff return (EFAULT); 182115765Sjeff 183115765Sjeff if (owner == MTX_CONTESTED); 184115765Sjeff return (0); 185115765Sjeff 186115765Sjeff /* If this failed the lock has changed, restart. */ 187115765Sjeff continue; 188112904Sjeff } 189112904Sjeff 190112904Sjeff 191115765Sjeff UMTX_LOCK(); 192115765Sjeff uq = umtx_insert(td, umtx); 193115765Sjeff UMTX_UNLOCK(); 194115765Sjeff 195112904Sjeff /* 196112904Sjeff * Set the contested bit so that a release in user space 197112904Sjeff * knows to use the system call for unlock. If this fails 198112904Sjeff * either some one else has acquired the lock or it has been 199112904Sjeff * released. 200112904Sjeff */ 201112967Sjake old = casuptr((intptr_t *)&umtx->u_owner, owner, 202112967Sjake owner | UMTX_CONTESTED); 203112904Sjeff 204112904Sjeff /* The address was invalid. */ 205112967Sjake if (old == -1) { 206115765Sjeff UMTX_LOCK(); 207115765Sjeff umtx_remove(uq, td); 208115765Sjeff UMTX_UNLOCK(); 209115765Sjeff return (EFAULT); 210112904Sjeff } 211112904Sjeff 212112904Sjeff /* 213115765Sjeff * We set the contested bit, sleep. Otherwise the lock changed 214115765Sjeff * and we need to retry. 215112904Sjeff */ 216115765Sjeff UMTX_LOCK(); 217115765Sjeff if (old == owner) 218115765Sjeff error = msleep(td, &umtx_lock, 219115765Sjeff td->td_priority | PCATCH, "umtx", 0); 220115765Sjeff else 221115765Sjeff error = 0; 222112904Sjeff 223115765Sjeff umtx_remove(uq, td); 224115765Sjeff UMTX_UNLOCK(); 225112904Sjeff 226112904Sjeff /* 227115765Sjeff * If we caught a signal we might have to retry or exit 228115765Sjeff * immediately. 229112904Sjeff */ 230112904Sjeff if (error) 231115765Sjeff return (error); 232112904Sjeff } 233112904Sjeff 234115765Sjeff return (0); 235112904Sjeff} 236112904Sjeff 237112904Sjeffint 238112904Sjeff_umtx_unlock(struct thread *td, struct _umtx_unlock_args *uap) 239112904Sjeff /* struct umtx *umtx */ 240112904Sjeff{ 241115765Sjeff struct thread *blocked; 242112904Sjeff struct umtx *umtx; 243115765Sjeff struct umtx_q *uq; 244112904Sjeff intptr_t owner; 245112967Sjake intptr_t old; 246112904Sjeff 247112904Sjeff umtx = uap->umtx; 248112904Sjeff 249112904Sjeff /* 250112904Sjeff * Make sure we own this mtx. 251112904Sjeff * 252112904Sjeff * XXX Need a {fu,su}ptr this is not correct on arch where 253112904Sjeff * sizeof(intptr_t) != sizeof(long). 254112904Sjeff */ 255115765Sjeff if ((owner = fuword(&umtx->u_owner)) == -1) 256115765Sjeff return (EFAULT); 257115765Sjeff 258115765Sjeff if ((struct thread *)(owner & ~UMTX_CONTESTED) != td) 259115765Sjeff return (EPERM); 260112904Sjeff /* 261112904Sjeff * If we own it but it isn't contested then we can just release and 262112904Sjeff * return. 263112904Sjeff */ 264112904Sjeff if ((owner & UMTX_CONTESTED) == 0) { 265112904Sjeff owner = casuptr((intptr_t *)&umtx->u_owner, 266112904Sjeff (intptr_t)td, UMTX_UNOWNED); 267112904Sjeff 268112904Sjeff if (owner == -1) 269115765Sjeff return (EFAULT); 270112904Sjeff /* 271112904Sjeff * If this failed someone modified the memory without going 272112904Sjeff * through this api. 273112904Sjeff */ 274115765Sjeff if (owner != (intptr_t)td) 275115765Sjeff return (EINVAL); 276112904Sjeff 277115765Sjeff return (0); 278112904Sjeff } 279112904Sjeff 280115765Sjeff old = casuptr((intptr_t *)&umtx->u_owner, owner, UMTX_CONTESTED); 281112904Sjeff 282115765Sjeff if (old == -1) 283115765Sjeff return (EFAULT); 284112904Sjeff 285112904Sjeff /* 286115765Sjeff * This will only happen if someone modifies the lock without going 287115765Sjeff * through this api. 288112904Sjeff */ 289115765Sjeff if (old != owner) 290115765Sjeff return (EINVAL); 291112904Sjeff 292112904Sjeff /* 293115765Sjeff * We have to wake up one of the blocked threads. 294112904Sjeff */ 295115765Sjeff UMTX_LOCK(); 296115765Sjeff uq = umtx_lookup(td, umtx); 297115765Sjeff if (uq != NULL) { 298115765Sjeff blocked = TAILQ_FIRST(&uq->uq_tdq); 299115765Sjeff wakeup(blocked); 300112904Sjeff } 301112904Sjeff 302115310Sjeff UMTX_UNLOCK(); 303112904Sjeff 304115765Sjeff return (0); 305112904Sjeff} 306