bertos/kern/sem.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2001, 2004 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 1999, 2000, 2001 Bernie Innocenti <bernie@codewiz.org>
  31  * -->
  32  *
  33  * \brief Semaphore based synchronization services.
  34  *
  35  * \author Bernie Innocenti <bernie@codewiz.org>
  36  */
  37
  38 #include "sem.h"
  39 #include <cfg/debug.h>
  40
  41 #include <cpu/irq.h> // ASSERT_IRQ_DISABLED()
  42
  43 #include <kern/proc.h>
  44 #include <kern/proc_p.h>
  45 #include <kern/signal.h>
  46
  47 INLINE void sem_verify(struct Semaphore *s)
  48 {
  49         (void)s;
  50         ASSERT(s);
  51         LIST_ASSERT_VALID(&s->wait_queue);
  52         ASSERT(s->nest_count >= 0);
  53         ASSERT(s->nest_count < 128);   // heuristic max
  54 }
  55
  56 #if CONFIG_KERN_PRI && CONFIG_KERN_PRI_INHERIT
  57
  58 #define proc_updatePri(proc) (proc_setPri(proc, (proc)->orig_pri))
  59
  60
  61 INLINE void pri_inheritBlock(Semaphore *s)
  62 {
  63         Process *owner = s->owner;
  64
  65         /*
  66          * Enqueue the blocking process in the owner's inheritance
  67          * list. Notice that such process might have inherited its
  68          * current priority from someone else.
  69          */
  70         current_process->inh_link.pri = __prio_proc(current_process);
  71         LIST_ENQUEUE(&owner->inh_list, &current_process->inh_link);
  72         current_process->inh_blocked_by = s;
  73
  74         /*
  75          * As long as a process has the power of boosting the priority
  76          * of its lock owner...
  77          */
  78         while (current_process->inh_link.pri > prio_proc(owner)) {
  79                 Process *p = owner;
  80
  81                  /* Boost the priority of the owner */
  82                 proc_updatePri(p);
  83
  84                 /* If the owner is not blocked, we're done */
  85                 if (!p->inh_blocked_by)
  86                         break;
  87
  88                 /*
  89                  * Otherwise update the position of the owner
  90                  * (which is `p' at each round!) in the inheritance
  91                  * list it lies in and set up `owner' for the
  92                  * next round.
  93                  */
  94                 REMOVE(&p->inh_link.link);
  95                 p->inh_link.pri = prio_proc(p);
  96                 owner = p->inh_blocked_by->owner;
  97                 LIST_ENQUEUE(&owner->inh_list, &p->inh_link);
  98         }
  99 }
 100
 101
 102 INLINE void pri_inheritUnblock(Semaphore *s, Process *proc)
 103 {
 104         Process *owner = s->owner;
 105         Node *n, *temp;
 106         Process *p;
 107
 108         /*
 109          * This process has nothing more to do on a priority
 110          * inheritance list.
 111          */
 112         REMOVE(&proc->inh_link.link);
 113         proc->inh_blocked_by = NULL;
 114
 115         /*
 116          * Each process in the former owner's priority inheritance
 117          * list that is blocked on 's' needs to be removed from
 118          * there and added to the priority inheritance list of
 119          * this process, since it's going to be the new owner for
 120          * that semaphore.
 121          */
 122         FOREACH_NODE_SAFE(n, temp, &owner->inh_list) {
 123                 p = containerof(n, Process, inh_link.link);
 124                 /* Ensures only the processes blocked on 's' are affected! */
 125                 if (p->inh_blocked_by == s) {
 126                         REMOVE(&p->inh_link.link);
 127                         LIST_ENQUEUE(&proc->inh_list, &p->inh_link);
 128
 129                         /* And again, update the priority of the new owner */
 130                         if (p->inh_link.pri > prio_proc(proc))
 131                                 proc_updatePri(proc);
 132                 }
 133         }
 134
 135         proc_updatePri(owner);
 136 }
 137 #else
 138 INLINE void pri_inheritBlock(UNUSED_ARG(Semaphore *, s))
 139 {
 140 }
 141
 142 INLINE void pri_inheritUnblock(UNUSED_ARG(Semaphore *, s), UNUSED_ARG(Process *, proc))
 143 {
 144 }
 145 #endif /* CONFIG_KERN_PRI_INHERIT */
 146
 147
 148 /**
 149  * \brief Initialize a Semaphore structure.
 150  */
 151 void sem_init(struct Semaphore *s)
 152 {
 153         LIST_INIT(&s->wait_queue);
 154         s->owner = NULL;
 155         s->nest_count = 0;
 156 }
 157
 158
 159 /**
 160  * \brief Attempt to lock a semaphore without waiting.
 161  *
 162  * \return true in case of success, false if the semaphore
 163  *         was already locked by someone else.
 164  *
 165  * \note   each call to sem_attempt() must be matched by a
 166  *         call to sem_release().
 167  *
 168  * \see sem_obtain() sem_release()
 169  */
 170 bool sem_attempt(struct Semaphore *s)
 171 {
 172         bool result = false;
 173
 174         proc_forbid();
 175         sem_verify(s);
 176         if ((!s->owner) || (s->owner == current_process))
 177         {
 178                 s->owner = current_process;
 179                 s->nest_count++;
 180                 result = true;
 181         }
 182         proc_permit();
 183
 184         return result;
 185 }
 186
 187
 188 /**
 189  * \brief Lock a semaphore.
 190  *
 191  * If the semaphore is already owned by another process, the caller
 192  * process will be enqueued into the waiting list and sleep until
 193  * the semaphore is available.
 194  *
 195  * \note Each call to sem_obtain() must be matched by a
 196  *       call to sem_release().
 197  *
 198  * \note This routine is optimized for highest speed in
 199  *       the most common case: the semaphore is free or locked
 200  *       by the calling process itself. Rearranging this code
 201  *       is probably a bad idea.
 202  *
 203  * \sa sem_release() sem_attempt()
 204  */
 205 void sem_obtain(struct Semaphore *s)
 206 {
 207         proc_forbid();
 208         sem_verify(s);
 209
 210         /* Is the semaphore already locked by another process? */
 211         if (UNLIKELY(s->owner && (s->owner != current_process)))
 212         {
 213                 /* Append calling process to the wait queue */
 214                 ADDTAIL(&s->wait_queue, (Node *)current_process);
 215
 216                 /* Trigger priority inheritance logic, if enabled */
 217                 pri_inheritBlock(s);
 218
 219                 /*
 220                  * We will wake up only when the current owner calls
 221                  * sem_release(). Then, the semaphore will already
 222                  * be locked for us.
 223                  */
 224                 proc_permit();
 225                 proc_switch();
 226         }
 227         else
 228         {
 229                 ASSERT(LIST_EMPTY(&s->wait_queue));
 230
 231                 /* The semaphore was free: lock it */
 232                 s->owner = current_process;
 233                 s->nest_count++;
 234                 proc_permit();
 235         }
 236 }
 237
 238
 239 /**
 240  * \brief Release a lock on a previously locked semaphore.
 241  *
 242  * If the nesting count of the semaphore reaches zero,
 243  * the next process waiting for it will be awaken.
 244  *
 245  * \note This routine is optimized for highest speed in
 246  *       the most common case: the semaphore has been locked just
 247  *       once and nobody else was waiting for it. Rearranging
 248  *       this code is probably a bad idea.
 249  *
 250  * \sa sem_obtain() sem_attempt()
 251  */
 252 void sem_release(struct Semaphore *s)
 253 {
 254         Process *proc = NULL;
 255
 256         proc_forbid();
 257         sem_verify(s);
 258
 259         ASSERT(s->owner == current_process);
 260
 261         /*
 262          * Decrement nesting count and check if the semaphore
 263          * has been fully unlocked.
 264          */
 265         if (--s->nest_count == 0)
 266         {
 267                 /* Give semaphore to the first applicant, if any */
 268                 if (UNLIKELY((proc = (Process *)list_remHead(&s->wait_queue))))
 269                 {
 270                         /* Undo the effects of priority inheritance, if enabled */
 271                         pri_inheritUnblock(s, proc);
 272
 273                         s->nest_count = 1;
 274                         s->owner = proc;
 275                 } else {
 276                         /* Disown semaphore */
 277                         s->owner = NULL;
 278                 }
 279         }
 280         proc_permit();
 281
 282         if (proc)
 283                 ATOMIC(proc_wakeup(proc));
 284 }