4 * This file is part of BeRTOS.
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.
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.
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
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.
29 * Copyright 2001, 2004 Develer S.r.l. (http://www.develer.com/)
30 * Copyright 1999, 2000, 2001 Bernie Innocenti <bernie@codewiz.org>
33 * \brief Semaphore based synchronization services.
35 * \author Bernie Innocenti <bernie@codewiz.org>
39 #include <cfg/debug.h>
41 #include <cpu/irq.h> // ASSERT_IRQ_DISABLED()
43 #include <kern/proc.h>
44 #include <kern/proc_p.h>
45 #include <kern/signal.h>
47 INLINE void sem_verify(struct Semaphore *s)
51 LIST_ASSERT_VALID(&s->wait_queue);
52 ASSERT(s->nest_count >= 0);
53 ASSERT(s->nest_count < 128); // heuristic max
56 #if CONFIG_KERN_PRI && CONFIG_KERN_PRI_INHERIT
58 #define proc_updatePri(proc) (proc_setPri(proc, (proc)->orig_pri))
62 * Priority inheritance update algorithm.
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.
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.
74 INLINE void pri_inheritBlock(Semaphore *s)
76 Process *owner = s->owner;
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.
83 current_process->inh_link.pri = __prio_proc(current_process);
84 LIST_ENQUEUE(&owner->inh_list, ¤t_process->inh_link);
85 current_process->inh_blocked_by = s;
88 * As long as a process has the power of boosting the priority
89 * of its lock owner...
91 while (current_process->inh_link.pri > prio_proc(owner)) {
94 /* Boost the priority of the owner */
97 /* If the owner is not blocked, we're done */
98 if (!p->inh_blocked_by)
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
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);
116 * Priority inheritance unblock algorithm.
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.
122 * \param proc The process that will take ownership of the semaphore.
124 INLINE void pri_inheritUnblock(Semaphore *s, Process *proc)
126 Process *owner = s->owner;
131 * This process has nothing more to do on a priority
134 REMOVE(&proc->inh_link.link);
135 proc->inh_blocked_by = NULL;
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
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);
151 /* And again, update the priority of the new owner */
152 if (p->inh_link.pri > prio_proc(proc))
153 proc_updatePri(proc);
157 proc_updatePri(owner);
160 INLINE void pri_inheritBlock(UNUSED_ARG(Semaphore *, s))
164 INLINE void pri_inheritUnblock(UNUSED_ARG(Semaphore *, s), UNUSED_ARG(Process *, proc))
167 #endif /* CONFIG_KERN_PRI_INHERIT */
171 * \brief Initialize a Semaphore structure.
173 void sem_init(struct Semaphore *s)
175 LIST_INIT(&s->wait_queue);
182 * \brief Attempt to lock a semaphore without waiting.
184 * \return true in case of success, false if the semaphore
185 * was already locked by someone else.
187 * \note each call to sem_attempt() must be matched by a
188 * call to sem_release().
190 * \see sem_obtain() sem_release()
192 bool sem_attempt(struct Semaphore *s)
198 if ((!s->owner) || (s->owner == current_process))
200 s->owner = current_process;
211 * \brief Lock a semaphore.
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.
217 * \note Each call to sem_obtain() must be matched by a
218 * call to sem_release().
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.
225 * \sa sem_release() sem_attempt()
227 void sem_obtain(struct Semaphore *s)
232 /* Is the semaphore already locked by another process? */
233 if (UNLIKELY(s->owner && (s->owner != current_process)))
235 /* Append calling process to the wait queue */
236 ADDTAIL(&s->wait_queue, (Node *)current_process);
238 /* Trigger priority inheritance logic, if enabled */
242 * We will wake up only when the current owner calls
243 * sem_release(). Then, the semaphore will already
251 ASSERT(LIST_EMPTY(&s->wait_queue));
253 /* The semaphore was free: lock it */
254 s->owner = current_process;
262 * \brief Release a lock on a previously locked semaphore.
264 * If the nesting count of the semaphore reaches zero,
265 * the next process waiting for it will be awaken.
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.
272 * \sa sem_obtain() sem_attempt()
274 void sem_release(struct Semaphore *s)
276 Process *proc = NULL;
281 ASSERT(s->owner == current_process);
284 * Decrement nesting count and check if the semaphore
285 * has been fully unlocked.
287 if (--s->nest_count == 0)
289 /* Give semaphore to the first applicant, if any */
290 if (UNLIKELY((proc = (Process *)list_remHead(&s->wait_queue))))
292 /* Undo the effects of priority inheritance, if enabled */
293 pri_inheritUnblock(s, proc);
298 /* Disown semaphore */
305 ATOMIC(proc_wakeup(proc));