Subversion Repositories HelenOS

Rev

Rev 2925 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2001-2004 Jakub Jermar
  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.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - 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.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /** @addtogroup sync
  30.  * @{
  31.  */
  32.  
  33. /**
  34.  * @file
  35.  * @brief   Wait queue.
  36.  *
  37.  * Wait queue is the basic synchronization primitive upon which all
  38.  * other synchronization primitives build.
  39.  *
  40.  * It allows threads to wait for an event in first-come, first-served
  41.  * fashion. Conditional operation as well as timeouts and interruptions
  42.  * are supported.
  43.  */
  44.  
  45. #include <synch/waitq.h>
  46. #include <synch/synch.h>
  47. #include <synch/spinlock.h>
  48. #include <proc/thread.h>
  49. #include <proc/scheduler.h>
  50. #include <arch/asm.h>
  51. #include <arch/types.h>
  52. #include <time/timeout.h>
  53. #include <arch.h>
  54. #include <context.h>
  55. #include <adt/list.h>
  56.  
  57. static void waitq_sleep_timed_out(void *data);
  58.  
  59. /** Initialize wait queue
  60.  *
  61.  * Initialize wait queue.
  62.  *
  63.  * @param wq        Pointer to wait queue to be initialized.
  64.  */
  65. void waitq_initialize(waitq_t *wq)
  66. {
  67.     spinlock_initialize(&wq->lock, "waitq_lock");
  68.     list_initialize(&wq->head);
  69.     wq->missed_wakeups = 0;
  70. }
  71.  
  72. /** Handle timeout during waitq_sleep_timeout() call
  73.  *
  74.  * This routine is called when waitq_sleep_timeout() times out.
  75.  * Interrupts are disabled.
  76.  *
  77.  * It is supposed to try to remove 'its' thread from the wait queue;
  78.  * it can eventually fail to achieve this goal when these two events
  79.  * overlap. In that case it behaves just as though there was no
  80.  * timeout at all.
  81.  *
  82.  * @param data      Pointer to the thread that called waitq_sleep_timeout().
  83.  */
  84. void waitq_sleep_timed_out(void *data)
  85. {
  86.     thread_t *t = (thread_t *) data;
  87.     waitq_t *wq;
  88.     bool do_wakeup = false;
  89.     DEADLOCK_PROBE_INIT(p_wqlock);
  90.  
  91.     spinlock_lock(&threads_lock);
  92.     if (!thread_exists(t))
  93.         goto out;
  94.  
  95. grab_locks:
  96.     spinlock_lock(&t->lock);
  97.     if ((wq = t->sleep_queue)) {        /* assignment */
  98.         if (!spinlock_trylock(&wq->lock)) {
  99.             spinlock_unlock(&t->lock);
  100.             DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
  101.             goto grab_locks;    /* avoid deadlock */
  102.         }
  103.  
  104.         list_remove(&t->wq_link);
  105.         t->saved_context = t->sleep_timeout_context;
  106.         do_wakeup = true;
  107.         t->sleep_queue = NULL;
  108.         spinlock_unlock(&wq->lock);
  109.     }
  110.    
  111.     t->timeout_pending = false;
  112.     spinlock_unlock(&t->lock);
  113.    
  114.     if (do_wakeup)
  115.         thread_ready(t);
  116.  
  117. out:
  118.     spinlock_unlock(&threads_lock);
  119. }
  120.  
  121. /** Interrupt sleeping thread.
  122.  *
  123.  * This routine attempts to interrupt a thread from its sleep in a waitqueue.
  124.  * If the thread is not found sleeping, no action is taken.
  125.  *
  126.  * @param t     Thread to be interrupted.
  127.  */
  128. void waitq_interrupt_sleep(thread_t *t)
  129. {
  130.     waitq_t *wq;
  131.     bool do_wakeup = false;
  132.     ipl_t ipl;
  133.     DEADLOCK_PROBE_INIT(p_wqlock);
  134.  
  135.     ipl = interrupts_disable();
  136.     spinlock_lock(&threads_lock);
  137.     if (!thread_exists(t))
  138.         goto out;
  139.  
  140. grab_locks:
  141.     spinlock_lock(&t->lock);
  142.     if ((wq = t->sleep_queue)) {        /* assignment */
  143.         if (!(t->sleep_interruptible)) {
  144.             /*
  145.              * The sleep cannot be interrupted.
  146.              */
  147.             spinlock_unlock(&t->lock);
  148.             goto out;
  149.         }
  150.            
  151.         if (!spinlock_trylock(&wq->lock)) {
  152.             spinlock_unlock(&t->lock);
  153.             DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
  154.             goto grab_locks;    /* avoid deadlock */
  155.         }
  156.  
  157.         if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
  158.             t->timeout_pending = false;
  159.  
  160.         list_remove(&t->wq_link);
  161.         t->saved_context = t->sleep_interruption_context;
  162.         do_wakeup = true;
  163.         t->sleep_queue = NULL;
  164.         spinlock_unlock(&wq->lock);
  165.     }
  166.     spinlock_unlock(&t->lock);
  167.  
  168.     if (do_wakeup)
  169.         thread_ready(t);
  170.  
  171. out:
  172.     spinlock_unlock(&threads_lock);
  173.     interrupts_restore(ipl);
  174. }
  175.  
  176. /** Sleep until either wakeup, timeout or interruption occurs
  177.  *
  178.  * This is a sleep implementation which allows itself to time out or to be
  179.  * interrupted from the sleep, restoring a failover context.
  180.  *
  181.  * Sleepers are organised in a FIFO fashion in a structure called wait queue.
  182.  *
  183.  * This function is really basic in that other functions as waitq_sleep()
  184.  * and all the *_timeout() functions use it.
  185.  *
  186.  * @param wq        Pointer to wait queue.
  187.  * @param usec      Timeout in microseconds.
  188.  * @param flags     Specify mode of the sleep.
  189.  *
  190.  * The sleep can be interrupted only if the
  191.  * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags.
  192.  *
  193.  * If usec is greater than zero, regardless of the value of the
  194.  * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either
  195.  * timeout, interruption or wakeup comes.
  196.  *
  197.  * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is not set in flags,
  198.  * the call will not return until wakeup or interruption comes.
  199.  *
  200.  * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is set in flags, the
  201.  * call will immediately return, reporting either success or failure.
  202.  *
  203.  * @return      Returns one of ESYNCH_WOULD_BLOCK, ESYNCH_TIMEOUT,
  204.  *          ESYNCH_INTERRUPTED, ESYNCH_OK_ATOMIC and
  205.  *          ESYNCH_OK_BLOCKED.
  206.  *
  207.  * @li  ESYNCH_WOULD_BLOCK means that the sleep failed because at the time of
  208.  *  the call there was no pending wakeup.
  209.  *
  210.  * @li  ESYNCH_TIMEOUT means that the sleep timed out.
  211.  *
  212.  * @li  ESYNCH_INTERRUPTED means that somebody interrupted the sleeping thread.
  213.  *
  214.  * @li  ESYNCH_OK_ATOMIC means that the sleep succeeded and that there was
  215.  *  a pending wakeup at the time of the call. The caller was not put
  216.  *  asleep at all.
  217.  *
  218.  * @li  ESYNCH_OK_BLOCKED means that the sleep succeeded; the full sleep was
  219.  *  attempted.
  220.  */
  221. int waitq_sleep_timeout(waitq_t *wq, uint32_t usec, int flags)
  222. {
  223.     ipl_t ipl;
  224.     int rc;
  225.    
  226.     ipl = waitq_sleep_prepare(wq);
  227.     rc = waitq_sleep_timeout_unsafe(wq, usec, flags);
  228.     waitq_sleep_finish(wq, rc, ipl);
  229.     return rc;
  230. }
  231.  
  232. /** Prepare to sleep in a waitq.
  233.  *
  234.  * This function will return holding the lock of the wait queue
  235.  * and interrupts disabled.
  236.  *
  237.  * @param wq        Wait queue.
  238.  *
  239.  * @return      Interrupt level as it existed on entry to this function.
  240.  */
  241. ipl_t waitq_sleep_prepare(waitq_t *wq)
  242. {
  243.     ipl_t ipl;
  244.    
  245. restart:
  246.     ipl = interrupts_disable();
  247.  
  248.     if (THREAD) {   /* needed during system initiailzation */
  249.         /*
  250.          * Busy waiting for a delayed timeout.
  251.          * This is an important fix for the race condition between
  252.          * a delayed timeout and a next call to waitq_sleep_timeout().
  253.          * Simply, the thread is not allowed to go to sleep if
  254.          * there are timeouts in progress.
  255.          */
  256.         spinlock_lock(&THREAD->lock);
  257.         if (THREAD->timeout_pending) {
  258.             spinlock_unlock(&THREAD->lock);
  259.             interrupts_restore(ipl);
  260.             goto restart;
  261.         }
  262.         spinlock_unlock(&THREAD->lock);
  263.     }
  264.                                                    
  265.     spinlock_lock(&wq->lock);
  266.     return ipl;
  267. }
  268.  
  269. /** Finish waiting in a wait queue.
  270.  *
  271.  * This function restores interrupts to the state that existed prior
  272.  * to the call to waitq_sleep_prepare(). If necessary, the wait queue
  273.  * lock is released.
  274.  *
  275.  * @param wq        Wait queue.
  276.  * @param rc        Return code of waitq_sleep_timeout_unsafe().
  277.  * @param ipl       Interrupt level returned by waitq_sleep_prepare().
  278.  */
  279. void waitq_sleep_finish(waitq_t *wq, int rc, ipl_t ipl)
  280. {
  281.     switch (rc) {
  282.     case ESYNCH_WOULD_BLOCK:
  283.     case ESYNCH_OK_ATOMIC:
  284.         spinlock_unlock(&wq->lock);
  285.         break;
  286.     default:
  287.         break;
  288.     }
  289.     interrupts_restore(ipl);
  290. }
  291.  
  292. /** Internal implementation of waitq_sleep_timeout().
  293.  *
  294.  * This function implements logic of sleeping in a wait queue.
  295.  * This call must be preceded by a call to waitq_sleep_prepare()
  296.  * and followed by a call to waitq_sleep_finish().
  297.  *
  298.  * @param wq        See waitq_sleep_timeout().
  299.  * @param usec      See waitq_sleep_timeout().
  300.  * @param flags     See waitq_sleep_timeout().
  301.  *
  302.  * @return      See waitq_sleep_timeout().
  303.  */
  304. int waitq_sleep_timeout_unsafe(waitq_t *wq, uint32_t usec, int flags)
  305. {
  306.     /* checks whether to go to sleep at all */
  307.     if (wq->missed_wakeups) {
  308.         wq->missed_wakeups--;
  309.         return ESYNCH_OK_ATOMIC;
  310.     }
  311.     else {
  312.         if ((flags & SYNCH_FLAGS_NON_BLOCKING) && (usec == 0)) {
  313.             /* return immediatelly instead of going to sleep */
  314.             return ESYNCH_WOULD_BLOCK;
  315.         }
  316.     }
  317.    
  318.     /*
  319.      * Now we are firmly decided to go to sleep.
  320.      */
  321.     spinlock_lock(&THREAD->lock);
  322.  
  323.     if (flags & SYNCH_FLAGS_INTERRUPTIBLE) {
  324.  
  325.         /*
  326.          * If the thread was already interrupted,
  327.          * don't go to sleep at all.
  328.          */
  329.         if (THREAD->interrupted) {
  330.             spinlock_unlock(&THREAD->lock);
  331.             spinlock_unlock(&wq->lock);
  332.             return ESYNCH_INTERRUPTED;
  333.         }
  334.  
  335.         /*
  336.          * Set context that will be restored if the sleep
  337.          * of this thread is ever interrupted.
  338.          */
  339.         THREAD->sleep_interruptible = true;
  340.         if (!context_save(&THREAD->sleep_interruption_context)) {
  341.             /* Short emulation of scheduler() return code. */
  342.             spinlock_unlock(&THREAD->lock);
  343.             return ESYNCH_INTERRUPTED;
  344.         }
  345.  
  346.     } else {
  347.         THREAD->sleep_interruptible = false;
  348.     }
  349.  
  350.     if (usec) {
  351.         /* We use the timeout variant. */
  352.         if (!context_save(&THREAD->sleep_timeout_context)) {
  353.             /* Short emulation of scheduler() return code. */
  354.             spinlock_unlock(&THREAD->lock);
  355.             return ESYNCH_TIMEOUT;
  356.         }
  357.         THREAD->timeout_pending = true;
  358.         timeout_register(&THREAD->sleep_timeout, (uint64_t) usec,
  359.             waitq_sleep_timed_out, THREAD);
  360.     }
  361.  
  362.     list_append(&THREAD->wq_link, &wq->head);
  363.  
  364.     /*
  365.      * Suspend execution.
  366.      */
  367.     THREAD->state = Sleeping;
  368.     THREAD->sleep_queue = wq;
  369.  
  370.     spinlock_unlock(&THREAD->lock);
  371.  
  372.     /* wq->lock is released in scheduler_separated_stack() */
  373.     scheduler();
  374.    
  375.     return ESYNCH_OK_BLOCKED;
  376. }
  377.  
  378.  
  379. /** Wake up first thread sleeping in a wait queue
  380.  *
  381.  * Wake up first thread sleeping in a wait queue. This is the SMP- and IRQ-safe
  382.  * wrapper meant for general use.
  383.  *
  384.  * Besides its 'normal' wakeup operation, it attempts to unregister possible
  385.  * timeout.
  386.  *
  387.  * @param wq        Pointer to wait queue.
  388.  * @param mode      Wakeup mode.
  389.  */
  390. void waitq_wakeup(waitq_t *wq, wakeup_mode_t mode)
  391. {
  392.     ipl_t ipl;
  393.  
  394.     ipl = interrupts_disable();
  395.     spinlock_lock(&wq->lock);
  396.  
  397.     _waitq_wakeup_unsafe(wq, mode);
  398.  
  399.     spinlock_unlock(&wq->lock);
  400.     interrupts_restore(ipl);
  401. }
  402.  
  403. /** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
  404.  *
  405.  * This is the internal SMP- and IRQ-unsafe version of waitq_wakeup(). It
  406.  * assumes wq->lock is already locked and interrupts are already disabled.
  407.  *
  408.  * @param wq        Pointer to wait queue.
  409.  * @param mode      If mode is WAKEUP_FIRST, then the longest waiting
  410.  *          thread, if any, is woken up. If mode is WAKEUP_ALL, then
  411.  *          all waiting threads, if any, are woken up. If there are
  412.  *          no waiting threads to be woken up, the missed wakeup is
  413.  *          recorded in the wait queue.
  414.  */
  415. void _waitq_wakeup_unsafe(waitq_t *wq, wakeup_mode_t mode)
  416. {
  417.     thread_t *t;
  418.     size_t count = 0;
  419.  
  420. loop:  
  421.     if (list_empty(&wq->head)) {
  422.         wq->missed_wakeups++;
  423.         if (count && mode == WAKEUP_ALL)
  424.             wq->missed_wakeups--;
  425.         return;
  426.     }
  427.  
  428.     count++;
  429.     t = list_get_instance(wq->head.next, thread_t, wq_link);
  430.    
  431.     /*
  432.      * Lock the thread prior to removing it from the wq.
  433.      * This is not necessary because of mutual exclusion
  434.      * (the link belongs to the wait queue), but because
  435.      * of synchronization with waitq_sleep_timed_out()
  436.      * and thread_interrupt_sleep().
  437.      *
  438.      * In order for these two functions to work, the following
  439.      * invariant must hold:
  440.      *
  441.      * t->sleep_queue != NULL <=> t sleeps in a wait queue
  442.      *
  443.      * For an observer who locks the thread, the invariant
  444.      * holds only when the lock is held prior to removing
  445.      * it from the wait queue.
  446.      */
  447.     spinlock_lock(&t->lock);
  448.     list_remove(&t->wq_link);
  449.    
  450.     if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
  451.         t->timeout_pending = false;
  452.     t->sleep_queue = NULL;
  453.     spinlock_unlock(&t->lock);
  454.  
  455.     thread_ready(t);
  456.  
  457.     if (mode == WAKEUP_ALL)
  458.         goto loop;
  459. }
  460.  
  461. /** @}
  462.  */
  463.