1 /* 2 * Copyright (c) 2002, Jeffrey Roberson <jeff@freebsd.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #include <sys/cdefs.h> 28 __FBSDID("$FreeBSD$"); 29 30 #include <sys/param.h> 31 #include <sys/kernel.h> 32 #include <sys/limits.h> 33 #include <sys/lock.h> 34 #include <sys/malloc.h> 35 #include <sys/mutex.h> 36 #include <sys/proc.h> 37 #include <sys/sysent.h> 38 #include <sys/systm.h> 39 #include <sys/sysproto.h> 40 #include <sys/thr.h> 41 #include <sys/umtx.h> 42 43 struct umtx_q { 44 LIST_ENTRY(umtx_q) uq_next; /* Linked list for the hash. */ 45 TAILQ_HEAD(, thread) uq_tdq; /* List of threads blocked here. */ 46 struct umtx *uq_umtx; /* Pointer key component. */ 47 pid_t uq_pid; /* Pid key component. */ 48 int uq_count; /* How many threads blocked. */ 49 }; 50 51 LIST_HEAD(umtx_head, umtx_q); 52 struct umtxq_chain { 53 struct mtx uc_lock; /* lock for this chain. */ 54 struct umtx_head uc_queues; /* List of sleep queues. */ 55 }; 56 57 #define GOLDEN_RATIO_PRIME 2654404609U 58 #define UMTX_CHAINS 128 59 #define UMTX_SHIFTS (__WORD_BIT - 7) 60 61 static struct umtxq_chain umtxq_chains[UMTX_CHAINS]; 62 static MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory"); 63 64 #define UMTX_CONTESTED LONG_MIN 65 66 static void umtx_init_chains(void *); 67 static int umtxq_hash(struct thread *, struct umtx *); 68 static void umtxq_lock(struct thread *td, struct umtx *key); 69 static void umtxq_unlock(struct thread *td, struct umtx *key); 70 static struct umtx_q *umtxq_lookup(struct thread *, struct umtx *); 71 static struct umtx_q *umtxq_insert(struct thread *, struct umtx *); 72 static int umtxq_count(struct thread *td, struct umtx *umtx); 73 static int umtx_sleep(struct thread *td, struct umtx *umtx, int priority, 74 const char *wmesg, int timo); 75 static void umtx_signal(struct thread *td, struct umtx *umtx); 76 77 SYSINIT(umtx, SI_SUB_LOCK, SI_ORDER_MIDDLE, umtx_init_chains, NULL); 78 79 static void 80 umtx_init_chains(void *arg __unused) 81 { 82 int i; 83 84 for (i = 0; i < UMTX_CHAINS; ++i) { 85 mtx_init(&umtxq_chains[i].uc_lock, "umtxq_lock", NULL, 86 MTX_DEF | MTX_DUPOK); 87 LIST_INIT(&umtxq_chains[i].uc_queues); 88 } 89 } 90 91 static inline int 92 umtxq_hash(struct thread *td, struct umtx *umtx) 93 { 94 unsigned n = (uintptr_t)umtx + td->td_proc->p_pid; 95 return (((n * GOLDEN_RATIO_PRIME) >> UMTX_SHIFTS) % UMTX_CHAINS); 96 } 97 98 static inline void 99 umtxq_lock(struct thread *td, struct umtx *key) 100 { 101 int chain = umtxq_hash(td, key); 102 mtx_lock(&umtxq_chains[chain].uc_lock); 103 } 104 105 static inline void 106 umtxq_unlock(struct thread *td, struct umtx *key) 107 { 108 int chain = umtxq_hash(td, key); 109 mtx_unlock(&umtxq_chains[chain].uc_lock); 110 } 111 112 static struct umtx_q * 113 umtxq_lookup(struct thread *td, struct umtx *umtx) 114 { 115 struct umtx_head *head; 116 struct umtx_q *uq; 117 pid_t pid; 118 int chain; 119 120 chain = umtxq_hash(td, umtx); 121 mtx_assert(&umtxq_chains[chain].uc_lock, MA_OWNED); 122 pid = td->td_proc->p_pid; 123 head = &umtxq_chains[chain].uc_queues; 124 LIST_FOREACH(uq, head, uq_next) { 125 if (uq->uq_pid == pid && uq->uq_umtx == umtx) 126 return (uq); 127 } 128 return (NULL); 129 } 130 131 /* 132 * Insert a thread onto the umtx queue. 133 */ 134 static struct umtx_q * 135 umtxq_insert(struct thread *td, struct umtx *umtx) 136 { 137 struct umtx_head *head; 138 struct umtx_q *uq, *ins = NULL; 139 pid_t pid; 140 int chain; 141 142 chain = umtxq_hash(td, umtx); 143 pid = td->td_proc->p_pid; 144 if ((uq = umtxq_lookup(td, umtx)) == NULL) { 145 umtxq_unlock(td, umtx); 146 ins = malloc(sizeof(*uq), M_UMTX, M_ZERO | M_WAITOK); 147 umtxq_lock(td, umtx); 148 149 /* 150 * Some one else could have succeeded while we were blocked 151 * waiting on memory. 152 */ 153 if ((uq = umtxq_lookup(td, umtx)) == NULL) { 154 head = &umtxq_chains[chain].uc_queues; 155 uq = ins; 156 uq->uq_pid = pid; 157 uq->uq_umtx = umtx; 158 uq->uq_count = 0; 159 LIST_INSERT_HEAD(head, uq, uq_next); 160 TAILQ_INIT(&uq->uq_tdq); 161 ins = NULL; 162 } 163 } 164 TAILQ_INSERT_TAIL(&uq->uq_tdq, td, td_umtx); 165 uq->uq_count++; 166 if (ins) { 167 umtxq_unlock(td, umtx); 168 free(ins, M_UMTX); 169 umtxq_lock(td, umtx); 170 } 171 return (uq); 172 } 173 174 /* 175 * Remove thread from umtx queue, umtx chain lock is also 176 * released. 177 */ 178 static void 179 umtx_remove(struct umtx_q *uq, struct thread *td, struct umtx *umtx) 180 { 181 int chain; 182 183 chain = umtxq_hash(td, umtx); 184 mtx_assert(&umtxq_chains[chain].uc_lock, MA_OWNED); 185 TAILQ_REMOVE(&uq->uq_tdq, td, td_umtx); 186 uq->uq_count--; 187 if (TAILQ_EMPTY(&uq->uq_tdq)) { 188 LIST_REMOVE(uq, uq_next); 189 umtxq_unlock(td, umtx); 190 free(uq, M_UMTX); 191 } else 192 umtxq_unlock(td, umtx); 193 } 194 195 static inline int 196 umtxq_count(struct thread *td, struct umtx *umtx) 197 { 198 struct umtx_q *uq; 199 int count = 0; 200 201 umtxq_lock(td, umtx); 202 if ((uq = umtxq_lookup(td, umtx)) != NULL) 203 count = uq->uq_count; 204 umtxq_unlock(td, umtx); 205 return (count); 206 } 207 208 static inline int 209 umtx_sleep(struct thread *td, struct umtx *umtx, int priority, 210 const char *wmesg, int timo) 211 { 212 int chain; 213 214 chain = umtxq_hash(td, umtx); 215 mtx_assert(&umtxq_chains[chain].uc_lock, MA_OWNED); 216 return (msleep(td, &umtxq_chains[chain].uc_lock, priority, 217 wmesg, timo)); 218 } 219 220 static void 221 umtx_signal(struct thread *td, struct umtx *umtx) 222 { 223 struct umtx_q *uq; 224 struct thread *blocked = NULL; 225 226 umtxq_lock(td, umtx); 227 if ((uq = umtxq_lookup(td, umtx)) != NULL) { 228 if ((blocked = TAILQ_FIRST(&uq->uq_tdq)) != NULL) { 229 mtx_lock_spin(&sched_lock); 230 blocked->td_flags |= TDF_UMTXWAKEUP; 231 mtx_unlock_spin(&sched_lock); 232 } 233 } 234 umtxq_unlock(td, umtx); 235 if (blocked != NULL) 236 wakeup(blocked); 237 } 238 239 int 240 _umtx_lock(struct thread *td, struct _umtx_lock_args *uap) 241 /* struct umtx *umtx */ 242 { 243 struct umtx_q *uq; 244 struct umtx *umtx; 245 intptr_t owner; 246 intptr_t old; 247 int error = 0; 248 249 uq = NULL; 250 251 /* 252 * Care must be exercised when dealing with this structure. It 253 * can fault on any access. 254 */ 255 umtx = uap->umtx; 256 257 for (;;) { 258 /* 259 * Try the uncontested case. This should be done in userland. 260 */ 261 owner = casuptr((intptr_t *)&umtx->u_owner, 262 UMTX_UNOWNED, td->td_tid); 263 264 /* The acquire succeeded. */ 265 if (owner == UMTX_UNOWNED) 266 return (0); 267 268 /* The address was invalid. */ 269 if (owner == -1) 270 return (EFAULT); 271 272 /* If no one owns it but it is contested try to acquire it. */ 273 if (owner == UMTX_CONTESTED) { 274 owner = casuptr((intptr_t *)&umtx->u_owner, 275 UMTX_CONTESTED, td->td_tid | UMTX_CONTESTED); 276 277 if (owner == UMTX_CONTESTED) 278 return (0); 279 280 /* The address was invalid. */ 281 if (owner == -1) 282 return (EFAULT); 283 284 /* If this failed the lock has changed, restart. */ 285 continue; 286 } 287 288 /* 289 * If we caught a signal, we have retried and now 290 * exit immediately. 291 */ 292 if (error) 293 return (error); 294 295 umtxq_lock(td, umtx); 296 uq = umtxq_insert(td, umtx); 297 umtxq_unlock(td, umtx); 298 299 /* 300 * Set the contested bit so that a release in user space 301 * knows to use the system call for unlock. If this fails 302 * either some one else has acquired the lock or it has been 303 * released. 304 */ 305 old = casuptr((intptr_t *)&umtx->u_owner, owner, 306 owner | UMTX_CONTESTED); 307 308 /* The address was invalid. */ 309 if (old == -1) { 310 umtxq_lock(td, umtx); 311 umtx_remove(uq, td, umtx); 312 /* unlocked by umtx_remove */ 313 return (EFAULT); 314 } 315 316 /* 317 * We set the contested bit, sleep. Otherwise the lock changed 318 * and we need to retry or we lost a race to the thread 319 * unlocking the umtx. 320 */ 321 umtxq_lock(td, umtx); 322 if (old == owner && (td->td_flags & TDF_UMTXWAKEUP) == 0) 323 error = umtx_sleep(td, umtx, td->td_priority | PCATCH, 324 "umtx", 0); 325 else 326 error = 0; 327 umtx_remove(uq, td, umtx); 328 /* unlocked by umtx_remove */ 329 330 if (td->td_flags & TDF_UMTXWAKEUP) { 331 /* 332 * If we were resumed by umtxq_unlock, we should retry 333 * to avoid a race. 334 */ 335 mtx_lock_spin(&sched_lock); 336 td->td_flags &= ~TDF_UMTXWAKEUP; 337 mtx_unlock_spin(&sched_lock); 338 continue; 339 } 340 341 /* 342 * If we caught a signal, exit immediately. 343 */ 344 if (error) 345 return (error); 346 } 347 348 return (0); 349 } 350 351 int 352 _umtx_unlock(struct thread *td, struct _umtx_unlock_args *uap) 353 /* struct umtx *umtx */ 354 { 355 struct umtx *umtx; 356 intptr_t owner; 357 intptr_t old; 358 int count; 359 360 umtx = uap->umtx; 361 362 /* 363 * Make sure we own this mtx. 364 * 365 * XXX Need a {fu,su}ptr this is not correct on arch where 366 * sizeof(intptr_t) != sizeof(long). 367 */ 368 if ((owner = fuword(&umtx->u_owner)) == -1) 369 return (EFAULT); 370 371 if ((owner & ~UMTX_CONTESTED) != td->td_tid) 372 return (EPERM); 373 374 /* We should only ever be in here for contested locks */ 375 if ((owner & UMTX_CONTESTED) == 0) 376 return (EINVAL); 377 378 /* 379 * When unlocking the umtx, it must be marked as unowned if 380 * there is zero or one thread only waiting for it. 381 * Otherwise, it must be marked as contested. 382 */ 383 old = casuptr((intptr_t *)&umtx->u_owner, owner, UMTX_UNOWNED); 384 if (old == -1) 385 return (EFAULT); 386 if (old != owner) 387 return (EINVAL); 388 389 /* 390 * At the point, a new thread can lock the umtx before we 391 * reach here, so contested bit will not be set, if there 392 * are two or more threads on wait queue, we should set 393 * contensted bit for them. 394 */ 395 count = umtxq_count(td, umtx); 396 if (count <= 0) 397 return (0); 398 399 /* 400 * If there is second thread waiting on umtx, set contested bit, 401 * if they are resumed before we reach here, it is harmless, 402 * just a bit unefficient. 403 */ 404 if (count > 1) { 405 owner = UMTX_UNOWNED; 406 for (;;) { 407 old = casuptr((intptr_t *)&umtx->u_owner, owner, 408 owner | UMTX_CONTESTED); 409 if (old == owner) 410 break; 411 if (old == -1) 412 return (EFAULT); 413 owner = old; 414 } 415 /* 416 * Another thread locked the umtx before us, so don't bother 417 * to wake more threads, that thread will do it when it unlocks 418 * the umtx. 419 */ 420 if ((owner & ~UMTX_CONTESTED) != 0) 421 return (0); 422 } 423 424 /* Wake blocked thread. */ 425 umtx_signal(td, umtx); 426 427 return (0); 428 } 429