Subversion Repositories HelenOS

Rev

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