Subversion Repositories HelenOS

Rev

Rev 557 | Rev 788 | 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. #include <synch/waitq.h>
  30. #include <synch/synch.h>
  31. #include <synch/spinlock.h>
  32. #include <proc/thread.h>
  33. #include <proc/scheduler.h>
  34. #include <arch/asm.h>
  35. #include <arch/types.h>
  36. #include <typedefs.h>
  37. #include <time/timeout.h>
  38. #include <arch.h>
  39. #include <context.h>
  40. #include <list.h>
  41.  
  42. /** Initialize wait queue
  43.  *
  44.  * Initialize wait queue.
  45.  *
  46.  * @param wq Pointer to wait queue to be initialized.
  47.  */
  48. void waitq_initialize(waitq_t *wq)
  49. {
  50.     spinlock_initialize(&wq->lock, "waitq_lock");
  51.     list_initialize(&wq->head);
  52.     wq->missed_wakeups = 0;
  53. }
  54.  
  55. /** Handle timeout during waitq_sleep_timeout() call
  56.  *
  57.  * This routine is called when waitq_sleep_timeout() timeouts.
  58.  * Interrupts are disabled.
  59.  *
  60.  * It is supposed to try to remove 'its' thread from the wait queue;
  61.  * it can eventually fail to achieve this goal when these two events
  62.  * overlap. In that case it behaves just as though there was no
  63.  * timeout at all.
  64.  *
  65.  * @param data Pointer to the thread that called waitq_sleep_timeout().
  66.  */
  67. void waitq_interrupted_sleep(void *data)
  68. {
  69.     thread_t *t = (thread_t *) data;
  70.     waitq_t *wq;
  71.     bool do_wakeup = false;
  72.  
  73.     spinlock_lock(&threads_lock);
  74.     if (!list_member(&t->threads_link, &threads_head))
  75.         goto out;
  76.  
  77. grab_locks:
  78.     spinlock_lock(&t->lock);
  79.     if ((wq = t->sleep_queue)) {        /* assignment */
  80.         if (!spinlock_trylock(&wq->lock)) {
  81.             spinlock_unlock(&t->lock);
  82.             goto grab_locks;    /* avoid deadlock */
  83.         }
  84.  
  85.         list_remove(&t->wq_link);
  86.         t->saved_context = t->sleep_timeout_context;
  87.         do_wakeup = true;
  88.        
  89.         spinlock_unlock(&wq->lock);
  90.         t->sleep_queue = NULL;
  91.     }
  92.    
  93.     t->timeout_pending = false;
  94.     spinlock_unlock(&t->lock);
  95.    
  96.     if (do_wakeup)
  97.         thread_ready(t);
  98.  
  99. out:
  100.     spinlock_unlock(&threads_lock);
  101. }
  102.  
  103. /** Sleep until either wakeup or timeout occurs
  104.  *
  105.  * This is a sleep implementation which allows itself to be
  106.  * interrupted from the sleep, restoring a failover context.
  107.  *
  108.  * Sleepers are organised in FIFO fashion in a structure called wait queue.
  109.  *
  110.  * This function is really basic in that other functions as waitq_sleep()
  111.  * and all the *_timeout() functions use it.
  112.  *
  113.  * @param wq Pointer to wait queue.
  114.  * @param usec Timeout in microseconds.
  115.  * @param nonblocking Blocking vs. non-blocking operation mode switch.
  116.  *
  117.  * If usec is greater than zero, regardless of the value of nonblocking,
  118.  * the call will not return until either timeout or wakeup comes.
  119.  *
  120.  * If usec is zero and nonblocking is zero (false), the call
  121.  * will not return until wakeup comes.
  122.  *
  123.  * If usec is zero and nonblocking is non-zero (true), the call will
  124.  * immediately return, reporting either success or failure.
  125.  *
  126.  * @return Returns one of: ESYNCH_WOULD_BLOCK, ESYNCH_TIMEOUT,
  127.  *         ESYNCH_OK_ATOMIC, ESYNCH_OK_BLOCKED.
  128.  *
  129.  * ESYNCH_WOULD_BLOCK means that the sleep failed because at the time
  130.  * of the call there was no pending wakeup.
  131.  *
  132.  * ESYNCH_TIMEOUT means that the sleep timed out.
  133.  *
  134.  * ESYNCH_OK_ATOMIC means that the sleep succeeded and that there was
  135.  * a pending wakeup at the time of the call. The caller was not put
  136.  * asleep at all.
  137.  *
  138.  * ESYNCH_OK_BLOCKED means that the sleep succeeded; the full sleep was
  139.  * attempted.
  140.  */
  141. int waitq_sleep_timeout(waitq_t *wq, __u32 usec, int nonblocking)
  142. {
  143.     volatile ipl_t ipl; /* must be live after context_restore() */
  144.    
  145.    
  146. restart:
  147.     ipl = interrupts_disable();
  148.    
  149.     /*
  150.      * Busy waiting for a delayed timeout.
  151.      * This is an important fix for the race condition between
  152.      * a delayed timeout and a next call to waitq_sleep_timeout().
  153.      * Simply, the thread is not allowed to go to sleep if
  154.      * there are timeouts in progress.
  155.      */
  156.     spinlock_lock(&THREAD->lock);
  157.     if (THREAD->timeout_pending) {
  158.         spinlock_unlock(&THREAD->lock);
  159.         interrupts_restore(ipl);       
  160.         goto restart;
  161.     }
  162.     spinlock_unlock(&THREAD->lock);
  163.    
  164.     spinlock_lock(&wq->lock);
  165.    
  166.     /* checks whether to go to sleep at all */
  167.     if (wq->missed_wakeups) {
  168.         wq->missed_wakeups--;
  169.         spinlock_unlock(&wq->lock);
  170.         interrupts_restore(ipl);
  171.         return ESYNCH_OK_ATOMIC;
  172.     }
  173.     else {
  174.         if (nonblocking && (usec == 0)) {
  175.             /* return immediatelly instead of going to sleep */
  176.             spinlock_unlock(&wq->lock);
  177.             interrupts_restore(ipl);
  178.             return ESYNCH_WOULD_BLOCK;
  179.         }
  180.     }
  181.  
  182.    
  183.     /*
  184.      * Now we are firmly decided to go to sleep.
  185.      */
  186.     spinlock_lock(&THREAD->lock);
  187.     if (usec) {
  188.         /* We use the timeout variant. */
  189.         if (!context_save(&THREAD->sleep_timeout_context)) {
  190.             /*
  191.              * Short emulation of scheduler() return code.
  192.              */
  193.             before_thread_runs();
  194.             spinlock_unlock(&THREAD->lock);
  195.             interrupts_restore(ipl);
  196.             return ESYNCH_TIMEOUT;
  197.         }
  198.         THREAD->timeout_pending = true;
  199.         timeout_register(&THREAD->sleep_timeout, (__u64) usec, waitq_interrupted_sleep, THREAD);
  200.     }
  201.  
  202.     list_append(&THREAD->wq_link, &wq->head);
  203.  
  204.     /*
  205.      * Suspend execution.
  206.      */
  207.     THREAD->state = Sleeping;
  208.     THREAD->sleep_queue = wq;
  209.  
  210.     spinlock_unlock(&THREAD->lock);
  211.  
  212.     scheduler();    /* wq->lock is released in scheduler_separated_stack() */
  213.     interrupts_restore(ipl);
  214.    
  215.     return ESYNCH_OK_BLOCKED;
  216. }
  217.  
  218.  
  219. /** Wake up first thread sleeping in a wait queue
  220.  *
  221.  * Wake up first thread sleeping in a wait queue.
  222.  * This is the SMP- and IRQ-safe wrapper meant for
  223.  * general use.
  224.  *
  225.  * Besides its 'normal' wakeup operation, it attempts
  226.  * to unregister possible timeout.
  227.  *
  228.  * @param wq Pointer to wait queue.
  229.  * @param all If this is non-zero, all sleeping threads
  230.  *        will be woken up and missed count will be zeroed.
  231.  */
  232. void waitq_wakeup(waitq_t *wq, bool all)
  233. {
  234.     ipl_t ipl;
  235.  
  236.     ipl = interrupts_disable();
  237.     spinlock_lock(&wq->lock);
  238.  
  239.     _waitq_wakeup_unsafe(wq, all);
  240.  
  241.     spinlock_unlock(&wq->lock);
  242.     interrupts_restore(ipl);   
  243. }
  244.  
  245. /** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
  246.  *
  247.  * This is the internal SMP- and IRQ-unsafe version
  248.  * of waitq_wakeup(). It assumes wq->lock is already
  249.  * locked and interrupts are already disabled.
  250.  *
  251.  * @param wq Pointer to wait queue.
  252.  * @param all If this is non-zero, all sleeping threads
  253.  *        will be woken up and missed count will be zeroed.
  254.  */
  255. void _waitq_wakeup_unsafe(waitq_t *wq, bool all)
  256. {
  257.     thread_t *t;
  258.  
  259. loop:  
  260.     if (list_empty(&wq->head)) {
  261.         wq->missed_wakeups++;
  262.         if (all)
  263.             wq->missed_wakeups = 0;
  264.         return;
  265.     }
  266.  
  267.     t = list_get_instance(wq->head.next, thread_t, wq_link);
  268.    
  269.     list_remove(&t->wq_link);
  270.     spinlock_lock(&t->lock);
  271.     if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
  272.         t->timeout_pending = false;
  273.     t->sleep_queue = NULL;
  274.     spinlock_unlock(&t->lock);
  275.  
  276.     thread_ready(t);
  277.  
  278.     if (all)
  279.         goto loop;
  280. }
  281.