kern_umtx.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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: releng/5.2/sys/kern/kern_umtx.c 119836 2003-09-07 11:14:52Z tjr $");
   29 
   30 #include <sys/param.h>
   31 #include <sys/kernel.h>
   32 #include <sys/lock.h>
   33 #include <sys/malloc.h>
   34 #include <sys/mutex.h>
   35 #include <sys/proc.h>
   36 #include <sys/signalvar.h>
   37 #include <sys/sysent.h>
   38 #include <sys/systm.h>
   39 #include <sys/sysproto.h>
   40 #include <sys/sx.h>
   41 #include <sys/thr.h>
   42 #include <sys/umtx.h>
   43 
   44 struct umtx_q {
   45         LIST_ENTRY(umtx_q)      uq_next;        /* Linked list for the hash. */
   46         TAILQ_HEAD(, thread) uq_tdq;    /* List of threads blocked here. */
   47         struct umtx     *uq_umtx;       /* Pointer key component. */
   48         pid_t           uq_pid;         /* Pid key component. */
   49 };
   50 
   51 #define UMTX_QUEUES     128
   52 #define UMTX_HASH(pid, umtx)                                            \
   53     (((uintptr_t)pid + ((uintptr_t)umtx & ~65535)) % UMTX_QUEUES)
   54 
   55 LIST_HEAD(umtx_head, umtx_q);
   56 static struct umtx_head queues[UMTX_QUEUES];
   57 static MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory");
   58 
   59 static struct mtx umtx_lock;
   60 MTX_SYSINIT(umtx, &umtx_lock, "umtx", MTX_DEF);
   61 
   62 #define UMTX_LOCK()     mtx_lock(&umtx_lock);
   63 #define UMTX_UNLOCK()   mtx_unlock(&umtx_lock);
   64 
   65 
   66 static struct umtx_q *umtx_lookup(struct thread *, struct umtx *umtx);
   67 static struct umtx_q *umtx_insert(struct thread *, struct umtx *umtx);
   68 
   69 static struct umtx_q *
   70 umtx_lookup(struct thread *td, struct umtx *umtx)
   71 {
   72         struct umtx_head *head;
   73         struct umtx_q *uq;
   74         pid_t pid;
   75 
   76         pid = td->td_proc->p_pid;
   77 
   78         head = &queues[UMTX_HASH(td->td_proc->p_pid, umtx)];
   79 
   80         LIST_FOREACH(uq, head, uq_next) {
   81                 if (uq->uq_pid == pid && uq->uq_umtx == umtx)
   82                         return (uq);
   83         }
   84 
   85         return (NULL);
   86 }
   87 
   88 /*
   89  * Insert a thread onto the umtx queue.
   90  */
   91 static struct umtx_q *
   92 umtx_insert(struct thread *td, struct umtx *umtx)
   93 {
   94         struct umtx_head *head;
   95         struct umtx_q *uq;
   96         pid_t pid;
   97 
   98         pid = td->td_proc->p_pid;
   99 
  100         if ((uq = umtx_lookup(td, umtx)) == NULL) {
  101                 struct umtx_q *ins;
  102 
  103                 UMTX_UNLOCK();
  104                 ins = malloc(sizeof(*uq), M_UMTX, M_ZERO | M_WAITOK);
  105                 UMTX_LOCK();
  106 
  107                 /*
  108                  * Some one else could have succeeded while we were blocked
  109                  * waiting on memory.
  110                  */
  111                 if ((uq = umtx_lookup(td, umtx)) == NULL) {
  112                         head = &queues[UMTX_HASH(pid, umtx)];
  113                         uq = ins;
  114                         uq->uq_pid = pid;
  115                         uq->uq_umtx = umtx;
  116                         LIST_INSERT_HEAD(head, uq, uq_next);
  117                         TAILQ_INIT(&uq->uq_tdq);
  118                 } else
  119                         free(ins, M_UMTX);
  120         }
  121 
  122         /*
  123          * Insert us onto the end of the TAILQ.
  124          */
  125         TAILQ_INSERT_TAIL(&uq->uq_tdq, td, td_umtx);
  126 
  127         return (uq);
  128 }
  129 
  130 static void
  131 umtx_remove(struct umtx_q *uq, struct thread *td)
  132 {
  133         TAILQ_REMOVE(&uq->uq_tdq, td, td_umtx);
  134 
  135         if (TAILQ_EMPTY(&uq->uq_tdq)) {
  136                 LIST_REMOVE(uq, uq_next);
  137                 free(uq, M_UMTX);
  138         }
  139 }
  140 
  141 int
  142 _umtx_lock(struct thread *td, struct _umtx_lock_args *uap)
  143     /* struct umtx *umtx */
  144 {
  145         struct umtx_q *uq;
  146         struct umtx *umtx;
  147         intptr_t owner;
  148         intptr_t old;
  149         int error;
  150 
  151         uq = NULL;
  152 
  153         /*
  154          * Care must be exercised when dealing with this structure.  It
  155          * can fault on any access.
  156          */
  157         umtx = uap->umtx;       
  158 
  159         for (;;) {
  160                 /*
  161                  * Try the uncontested case.  This should be done in userland.
  162                  */
  163                 owner = casuptr((intptr_t *)&umtx->u_owner,
  164                     UMTX_UNOWNED, (intptr_t)td);
  165 
  166                 /* The address was invalid. */
  167                 if (owner == -1)
  168                         return (EFAULT);
  169 
  170                 /* The acquire succeeded. */
  171                 if (owner == UMTX_UNOWNED)
  172                         return (0);
  173 
  174                 /* If no one owns it but it is contested try to acquire it. */
  175                 if (owner == UMTX_CONTESTED) {
  176                         owner = casuptr((intptr_t *)&umtx->u_owner,
  177                             UMTX_CONTESTED, ((intptr_t)td | UMTX_CONTESTED));
  178 
  179                         /* The address was invalid. */
  180                         if (owner == -1)
  181                                 return (EFAULT);
  182 
  183                         if (owner == UMTX_CONTESTED)
  184                                 return (0);
  185 
  186                         /* If this failed the lock has changed, restart. */
  187                         continue;
  188                 }
  189 
  190 
  191                 UMTX_LOCK();
  192                 uq = umtx_insert(td, umtx);
  193                 UMTX_UNLOCK();
  194 
  195                 /*
  196                  * Set the contested bit so that a release in user space
  197                  * knows to use the system call for unlock.  If this fails
  198                  * either some one else has acquired the lock or it has been
  199                  * released.
  200                  */
  201                 old = casuptr((intptr_t *)&umtx->u_owner, owner,
  202                     owner | UMTX_CONTESTED);
  203 
  204                 /* The address was invalid. */
  205                 if (old == -1) {
  206                         UMTX_LOCK();
  207                         umtx_remove(uq, td);
  208                         UMTX_UNLOCK();
  209                         return (EFAULT);
  210                 }
  211 
  212                 /*
  213                  * We set the contested bit, sleep. Otherwise the lock changed
  214                  * and we need to retry or we lost a race to the thread
  215                  * unlocking the umtx.
  216                  */
  217                 UMTX_LOCK();
  218                 mtx_lock_spin(&sched_lock);
  219                 if (old == owner && (td->td_flags & TDF_UMTXWAKEUP) == 0) {
  220                         mtx_unlock_spin(&sched_lock);
  221                         error = msleep(td, &umtx_lock,
  222                             td->td_priority | PCATCH, "umtx", 0);
  223                         mtx_lock_spin(&sched_lock);
  224                 } else
  225                         error = 0;
  226                 td->td_flags &= ~TDF_UMTXWAKEUP;
  227                 mtx_unlock_spin(&sched_lock);
  228 
  229                 umtx_remove(uq, td);
  230                 UMTX_UNLOCK();
  231 
  232                 /*
  233                  * If we caught a signal we might have to retry or exit 
  234                  * immediately.
  235                  */
  236                 if (error)
  237                         return (error);
  238         }
  239 
  240         return (0);
  241 }
  242 
  243 int
  244 _umtx_unlock(struct thread *td, struct _umtx_unlock_args *uap)
  245     /* struct umtx *umtx */
  246 {
  247         struct thread *blocked;
  248         struct umtx *umtx;
  249         struct umtx_q *uq;
  250         intptr_t owner;
  251         intptr_t old;
  252 
  253         umtx = uap->umtx;
  254 
  255         /*
  256          * Make sure we own this mtx.
  257          *
  258          * XXX Need a {fu,su}ptr this is not correct on arch where
  259          * sizeof(intptr_t) != sizeof(long).
  260          */
  261         if ((owner = fuword(&umtx->u_owner)) == -1)
  262                 return (EFAULT);
  263 
  264         if ((struct thread *)(owner & ~UMTX_CONTESTED) != td)
  265                 return (EPERM);
  266 
  267         /* We should only ever be in here for contested locks */
  268         if ((owner & UMTX_CONTESTED) == 0)
  269                 return (EINVAL);
  270         blocked = NULL;
  271 
  272         /*
  273          * When unlocking the umtx, it must be marked as unowned if
  274          * there is zero or one thread only waiting for it.
  275          * Otherwise, it must be marked as contested.
  276          */
  277         UMTX_LOCK();
  278         uq = umtx_lookup(td, umtx);
  279         if (uq == NULL ||
  280             (uq != NULL && (blocked = TAILQ_FIRST(&uq->uq_tdq)) != NULL &&
  281             TAILQ_NEXT(blocked, td_umtx) == NULL)) {
  282                 UMTX_UNLOCK();
  283                 old = casuptr((intptr_t *)&umtx->u_owner, owner,
  284                     UMTX_UNOWNED);
  285                 if (old == -1)
  286                         return (EFAULT);
  287                 if (old != owner)
  288                         return (EINVAL);
  289 
  290                 /*
  291                  * Recheck the umtx queue to make sure another thread
  292                  * didn't put itself on it after it was unlocked.
  293                  */
  294                 UMTX_LOCK();
  295                 uq = umtx_lookup(td, umtx);
  296                 if (uq != NULL &&
  297                     ((blocked = TAILQ_FIRST(&uq->uq_tdq)) != NULL &&
  298                     TAILQ_NEXT(blocked, td_umtx) != NULL)) {
  299                         UMTX_UNLOCK();
  300                         old = casuptr((intptr_t *)&umtx->u_owner,
  301                             UMTX_UNOWNED, UMTX_CONTESTED);
  302                 } else {
  303                         UMTX_UNLOCK();
  304                 }
  305         } else {
  306                 UMTX_UNLOCK();
  307                 old = casuptr((intptr_t *)&umtx->u_owner,
  308                     owner, UMTX_CONTESTED);
  309                 if (old != -1 && old != owner)
  310                         return (EINVAL);
  311         }
  312 
  313         if (old == -1)
  314                 return (EFAULT);
  315 
  316         /*
  317          * If there is a thread waiting on the umtx, wake it up.
  318          */
  319         if (blocked != NULL) {
  320                 mtx_lock_spin(&sched_lock);
  321                 blocked->td_flags |= TDF_UMTXWAKEUP;
  322                 mtx_unlock_spin(&sched_lock);
  323                 wakeup(blocked);
  324         }
  325 
  326         return (0);
  327 }
Cache object: 03ab5356df1fee834d1d1284c046bb74
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/kern/kern_umtx.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_umtx.c
