1  /*
   2   * \brief  Semaphore
   3   * \author Norman Feske
   4   * \author Christian Prochaska
   5   * \date   2006-09-22
   6   */
   7  
   8  /*
   9   * Copyright (C) 2006-2013 Genode Labs GmbH
  10   *
  11   * This file is part of the Genode OS framework, which is distributed
  12   * under the terms of the GNU General Public License version 2.
  13   */
  14  
  15  #ifndef _INCLUDE__BASE__SEMAPHORE_H_
  16  #define _INCLUDE__BASE__SEMAPHORE_H_
  17  
  18  #include <base/lock.h>
  19  #include <util/list.h>
  20  #include <util/fifo.h>
  21  
  22  namespace Genode {
  23  
  24     /**
  25      * Semaphore queue interface
  26      */
  27     class Semaphore_queue
  28     {
  29        public:
  30  
  31           /**
  32            * Semaphore-queue elements
  33            *
  34            * A queue element represents a thread blocking on the
  35            * semaphore.
  36            */
  37           class Element : Lock
  38           {
  39              public:
  40  
  41                 /**
  42                  * Constructor
  43                  */
  44                 Element() : Lock(LOCKED) { }
  45  
  46                 void block()   { lock();   }
  47                 void wake_up() { unlock(); }
  48           };
  49  
  50           /**
  51            * Add new queue member that is going to block
  52            */
  53           void enqueue(Element *e);
  54  
  55           /**
  56            * Dequeue queue member to wake up next
  57            */
  58           Element *dequeue();
  59     };
  60  
  61  
  62     /**
  63      * First-in-first-out variant of the semaphore-queue interface
  64      */
  65     class Fifo_semaphore_queue : public Semaphore_queue
  66     {
  67        public:
  68  
  69           class Element : public Semaphore_queue::Element,
  70                           public Fifo<Element>::Element { };
  71  
  72        private:
  73  
  74           Fifo<Element> _fifo;
  75  
  76        public:
  77  
  78           void enqueue(Element *e) { _fifo.enqueue(e); }
  79  
  80           Element *dequeue()  { return _fifo.dequeue(); }
  81     };
  82  
  83  
  84     /**
  85      * Semaphore base template
  86      *
  87      * \param QT  semaphore wait queue type implementing the
  88      *            `Semaphore_queue` interface
  89      * \param QTE wait-queue element type implementing the
  90      *            `Semaphore_queue::Element` interface
  91      *
  92      * The queuing policy is defined via the QT and QTE types.
  93      * This way, the platform-specific semaphore-queueing policies
  94      * such as priority-sorted queueing can be easily supported.
  95      */
  96     template <typename QT, typename QTE>
  97     class Semaphore_template
  98     {
  99        protected:
 100  
 101           int  _cnt;
 102           Lock _meta_lock;
 103           QT   _queue;
 104  
 105        public:
 106  
 107           /**
 108            * Constructor
 109            *
 110            * \param n  initial counter value of the semphore
 111            */
 112           Semaphore_template(int n = 0) : _cnt(n) { }
 113  
 114           ~Semaphore_template()
 115           {
 116              /* synchronize destruction with unfinished `up()` */
 117              try { _meta_lock.lock(); } catch (...) { }
 118           }
 119  
 120           void up()
 121           {
 122              Lock::Guard lock_guard(_meta_lock);
 123  
 124              if (++_cnt > 0)
 125                 return;
 126  
 127              /*
 128               * Remove element from queue and wake up the corresponding
 129               * blocking thread
 130               */
 131              Semaphore_queue::Element * element = _queue.dequeue();
 132              if (element)
 133                 element->wake_up();
 134           }
 135  
 136           void down()
 137           {
 138              _meta_lock.lock();
 139  
 140              if (--_cnt < 0) {
 141  
 142                 /*
 143                  * Create semaphore queue element representing the thread
 144                  * in the wait queue.
 145                  */
 146                 QTE queue_element;
 147                 _queue.enqueue(&queue_element);
 148                 _meta_lock.unlock();
 149  
 150                 /*
 151                  * The thread is going to block on a local lock now,
 152                  * waiting for getting waked from another thread
 153                  * calling `up()`
 154                  * */
 155                 queue_element.block();
 156  
 157              } else {
 158                 _meta_lock.unlock();
 159              }
 160           }
 161  
 162           /**
 163            * Return current semaphore counter
 164            */
 165           int cnt() { return _cnt; }
 166     };
 167  
 168  
 169     /**
 170      * Semaphore with default behaviour
 171      */
 172     typedef Semaphore_template<Fifo_semaphore_queue, Fifo_semaphore_queue::Element> Semaphore;
 173  }
 174  
 175  #endif /* _INCLUDE__BASE__SEMAPHORE_H_ */