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 /**
  62  * Priority inheritance update algorithm.
  63  *
  64  * The algorithm checks and boosts the priority of the semaphore's
  65  * current owner and also processes in that block the owner, which
  66  * form a chain of blocking processes.
  67  *
  68  * Note that the priority of a process in the chain of blocked
  69  * processes is always greater or equal than the priority of a process
  70  * before in the chain. See the diagram below:
  71  * P1  --. S1 ---> P2 --. S2 ---> P3
  72  * prio_proc(P2) >= prio_proc(P1) always.
  73  */
  74 INLINE void pri_inheritBlock(Semaphore *s)
  75 {
  76         Process *owner = s->owner;
  77
  78         /*
  79          * Enqueue the blocking process in the owner's inheritance
  80          * list. Notice that such process might have inherited its
  81          * current priority from someone else.
  82          */
  83         current_process->inh_link.pri = __prio_proc(current_process);
  84         LIST_ENQUEUE(&owner->inh_list, &current_process->inh_link);
  85         current_process->inh_blocked_by = s;
  86
  87         /*
  88          * As long as a process has the power of boosting the priority
  89          * of its lock owner...
  90          */
  91         while (current_process->inh_link.pri > prio_proc(owner)) {
  92                 Process *p = owner;
  93
  94                  /* Boost the priority of the owner */
  95                 proc_updatePri(p);
  96
  97                 /* If the owner is not blocked, we're done */
  98                 if (!p->inh_blocked_by)
  99                         break;
 100
 101                 /*
 102                  * Otherwise update the position of the owner
 103                  * (which is `p' at each round!) in the inheritance
 104                  * list it lies in and set up `owner' for the
 105                  * next round.
 106                  */
 107                 REMOVE(&p->inh_link.link);
 108                 p->inh_link.pri = prio_proc(p);
 109                 owner = p->inh_blocked_by->owner;
 110                 LIST_ENQUEUE(&owner->inh_list, &p->inh_link);
 111         }
 112 }
 113
 114
 115 /**
 116  * Priority inheritance unblock algorithm.
 117  *
 118  * Pass the priority inheritance list from the current owner to the
 119  * process that will take ownership of the semaphore next, potentially
 120  * boosting its priority.
 121  *
 122  * \param proc The process that will take ownership of the semaphore.
 123  */
 124 INLINE void pri_inheritUnblock(Semaphore *s, Process *proc)
 125 {
 126         Process *owner = s->owner;
 127         Node *n, *temp;
 128         Process *p;
 129
 130         /*
 131          * This process has nothing more to do on a priority
 132          * inheritance list.
 133          */
 134         REMOVE(&proc->inh_link.link);
 135         proc->inh_blocked_by = NULL;
 136
 137         /*
 138          * Each process in the former owner's priority inheritance
 139          * list that is blocked on 's' needs to be removed from
 140          * there and added to the priority inheritance list of
 141          * this process, since it's going to be the new owner for
 142          * that semaphore.
 143          */
 144         FOREACH_NODE_SAFE(n, temp, &owner->inh_list) {
 145                 p = containerof(n, Process, inh_link.link);
 146                 /* Ensures only the processes blocked on 's' are affected! */
 147                 if (p->inh_blocked_by == s) {
 148                         REMOVE(&p->inh_link.link);
 149                         LIST_ENQUEUE(&proc->inh_list, &p->inh_link);
 150
 151                         /* And again, update the priority of the new owner */
 152                         if (p->inh_link.pri > prio_proc(proc))
 153                                 proc_updatePri(proc);
 154                 }
 155         }
 156
 157         proc_updatePri(owner);
 158 }
 159 #else
 160 INLINE void pri_inheritBlock(UNUSED_ARG(Semaphore *, s))
 161 {
 162 }
 163
 164 INLINE void pri_inheritUnblock(UNUSED_ARG(Semaphore *, s), UNUSED_ARG(Process *, proc))
 165 {
 166 }
 167 #endif /* CONFIG_KERN_PRI_INHERIT */
 168
 169
 170 /**
 171  * \brief Initialize a Semaphore structure.
 172  */
 173 void sem_init(struct Semaphore *s)
 174 {
 175         LIST_INIT(&s->wait_queue);
 176         s->owner = NULL;
 177         s->nest_count = 0;
 178 }
 179
 180
 181 /**
 182  * \brief Attempt to lock a semaphore without waiting.
 183  *
 184  * \return true in case of success, false if the semaphore
 185  *         was already locked by someone else.
 186  *
 187  * \note   each call to sem_attempt() must be matched by a
 188  *         call to sem_release().
 189  *
 190  * \see sem_obtain() sem_release()
 191  */
 192 bool sem_attempt(struct Semaphore *s)
 193 {
 194         bool result = false;
 195
 196         proc_forbid();
 197         sem_verify(s);
 198         if ((!s->owner) || (s->owner == current_process))
 199         {
 200                 s->owner = current_process;
 201                 s->nest_count++;
 202                 result = true;
 203         }
 204         proc_permit();
 205
 206         return result;
 207 }
 208
 209
 210 /**
 211  * \brief Lock a semaphore.
 212  *
 213  * If the semaphore is already owned by another process, the caller
 214  * process will be enqueued into the waiting list and sleep until
 215  * the semaphore is available.
 216  *
 217  * \note Each call to sem_obtain() must be matched by a
 218  *       call to sem_release().
 219  *
 220  * \note This routine is optimized for highest speed in
 221  *       the most common case: the semaphore is free or locked
 222  *       by the calling process itself. Rearranging this code
 223  *       is probably a bad idea.
 224  *
 225  * \sa sem_release() sem_attempt()
 226  */
 227 void sem_obtain(struct Semaphore *s)
 228 {
 229         proc_forbid();
 230         sem_verify(s);
 231
 232         /* Is the semaphore already locked by another process? */
 233         if (UNLIKELY(s->owner && (s->owner != current_process)))
 234         {
 235                 /* Append calling process to the wait queue */
 236                 ADDTAIL(&s->wait_queue, (Node *)current_process);
 237
 238                 /* Trigger priority inheritance logic, if enabled */
 239                 pri_inheritBlock(s);
 240
 241                 /*
 242                  * We will wake up only when the current owner calls
 243                  * sem_release(). Then, the semaphore will already
 244                  * be locked for us.
 245                  */
 246                 proc_permit();
 247                 proc_switch();
 248         }
 249         else
 250         {
 251                 ASSERT(LIST_EMPTY(&s->wait_queue));
 252
 253                 /* The semaphore was free: lock it */
 254                 s->owner = current_process;
 255                 s->nest_count++;
 256                 proc_permit();
 257         }
 258 }
 259
 260
 261 /**
 262  * \brief Release a lock on a previously locked semaphore.
 263  *
 264  * If the nesting count of the semaphore reaches zero,
 265  * the next process waiting for it will be awaken.
 266  *
 267  * \note This routine is optimized for highest speed in
 268  *       the most common case: the semaphore has been locked just
 269  *       once and nobody else was waiting for it. Rearranging
 270  *       this code is probably a bad idea.
 271  *
 272  * \sa sem_obtain() sem_attempt()
 273  */
 274 void sem_release(struct Semaphore *s)
 275 {
 276         Process *proc = NULL;
 277
 278         proc_forbid();
 279         sem_verify(s);
 280
 281         ASSERT(s->owner == current_process);
 282
 283         /*
 284          * Decrement nesting count and check if the semaphore
 285          * has been fully unlocked.
 286          */
 287         if (--s->nest_count == 0)
 288         {
 289                 /* Give semaphore to the first applicant, if any */
 290                 if (UNLIKELY((proc = (Process *)list_remHead(&s->wait_queue))))
 291                 {
 292                         /* Undo the effects of priority inheritance, if enabled */
 293                         pri_inheritUnblock(s, proc);
 294
 295                         s->nest_count = 1;
 296                         s->owner = proc;
 297                 } else {
 298                         /* Disown semaphore */
 299                         s->owner = NULL;
 300                 }
 301         }
 302         proc_permit();
 303
 304         if (proc)
 305                 ATOMIC(proc_wakeup(proc));
 306 }