00001
00038 #include "sem.h"
00039 #include <cfg/debug.h>
00040
00041 #include <cpu/irq.h> // ASSERT_IRQ_DISABLED()
00042
00043 #include <kern/proc.h>
00044 #include <kern/proc_p.h>
00045 #include <kern/signal.h>
00046
00047 INLINE void sem_verify(struct Semaphore *s)
00048 {
00049     (void)s;
00050     ASSERT(s);
00051     LIST_ASSERT_VALID(&s->wait_queue);
00052     ASSERT(s->nest_count >= 0);
00053     ASSERT(s->nest_count < 128);   // heuristic max
00054 }
00055
00056 #if CONFIG_KERN_PRI && CONFIG_KERN_PRI_INHERIT
00057 
00058 #define proc_updatePri(proc) (proc_setPri(proc, (proc)->orig_pri))
00059 
00060
00074 INLINE void pri_inheritBlock(Semaphore *s)
00075 {
00076     Process *owner = s->owner;
00077
00078     /*
00079      * Enqueue the blocking process in the owner's inheritance
00080      * list. Notice that such process might have inherited its
00081      * current priority from someone else.
00082      */
00083     current_process->inh_link.pri = __prio_proc(current_process);
00084     LIST_ENQUEUE(&owner->inh_list, &current_process->inh_link);
00085     current_process->inh_blocked_by = s;
00086
00087     /*
00088      * As long as a process has the power of boosting the priority
00089      * of its lock owner...
00090      */
00091     while (current_process->inh_link.pri > prio_proc(owner)) {
00092         Process *p = owner;
00093
00094          /* Boost the priority of the owner */
00095         proc_updatePri(p);
00096
00097         /* If the owner is not blocked, we're done */
00098         if (!p->inh_blocked_by)
00099             break;
00100
00101         /*
00102          * Otherwise update the position of the owner
00103          * (which is `p' at each round!) in the inheritance
00104          * list it lies in and set up `owner' for the
00105          * next round.
00106          */
00107         REMOVE(&p->inh_link.link);
00108         p->inh_link.pri = prio_proc(p);
00109         owner = p->inh_blocked_by->owner;
00110         LIST_ENQUEUE(&owner->inh_list, &p->inh_link);
00111     }
00112 }
00113
00114
00124 INLINE void pri_inheritUnblock(Semaphore *s, Process *proc)
00125 {
00126     Process *owner = s->owner;
00127     Node *n, *temp;
00128     Process *p;
00129
00130     /*
00131      * This process has nothing more to do on a priority
00132      * inheritance list.
00133      */
00134     REMOVE(&proc->inh_link.link);
00135     proc->inh_blocked_by = NULL;
00136
00137     /*
00138      * Each process in the former owner's priority inheritance
00139      * list that is blocked on 's' needs to be removed from
00140      * there and added to the priority inheritance list of
00141      * this process, since it's going to be the new owner for
00142      * that semaphore.
00143      */
00144     FOREACH_NODE_SAFE(n, temp, &owner->inh_list) {
00145         p = containerof(n, Process, inh_link.link);
00146         /* Ensures only the processes blocked on 's' are affected! */
00147         if (p->inh_blocked_by == s) {
00148             REMOVE(&p->inh_link.link);
00149             LIST_ENQUEUE(&proc->inh_list, &p->inh_link);
00150
00151             /* And again, update the priority of the new owner */
00152             if (p->inh_link.pri > prio_proc(proc))
00153                 proc_updatePri(proc);
00154         }
00155     }
00156
00157     proc_updatePri(owner);
00158 }
00159 #else
00160 INLINE void pri_inheritBlock(UNUSED_ARG(Semaphore *, s))
00161 {
00162 }
00163
00164 INLINE void pri_inheritUnblock(UNUSED_ARG(Semaphore *, s), UNUSED_ARG(Process *, proc))
00165 {
00166 }
00167 #endif /* CONFIG_KERN_PRI_INHERIT */
00168
00169
00173 void sem_init(struct Semaphore *s)
00174 {
00175     LIST_INIT(&s->wait_queue);
00176     s->owner = NULL;
00177     s->nest_count = 0;
00178 }
00179
00180
00192 bool sem_attempt(struct Semaphore *s)
00193 {
00194     bool result = false;
00195
00196     proc_forbid();
00197     sem_verify(s);
00198     if ((!s->owner) || (s->owner == current_process))
00199     {
00200         s->owner = current_process;
00201         s->nest_count++;
00202         result = true;
00203     }
00204     proc_permit();
00205
00206     return result;
00207 }
00208
00209
00227 void sem_obtain(struct Semaphore *s)
00228 {
00229     proc_forbid();
00230     sem_verify(s);
00231
00232     /* Is the semaphore already locked by another process? */
00233     if (UNLIKELY(s->owner && (s->owner != current_process)))
00234     {
00235         /* Append calling process to the wait queue */
00236         ADDTAIL(&s->wait_queue, (Node *)current_process);
00237
00238         /* Trigger priority inheritance logic, if enabled */
00239         pri_inheritBlock(s);
00240
00241         /*
00242          * We will wake up only when the current owner calls
00243          * sem_release(). Then, the semaphore will already
00244          * be locked for us.
00245          */
00246         proc_permit();
00247         proc_switch();
00248     }
00249     else
00250     {
00251         ASSERT(LIST_EMPTY(&s->wait_queue));
00252
00253         /* The semaphore was free: lock it */
00254         s->owner = current_process;
00255         s->nest_count++;
00256         proc_permit();
00257     }
00258 }
00259
00260
00274 void sem_release(struct Semaphore *s)
00275 {
00276     Process *proc = NULL;
00277
00278     proc_forbid();
00279     sem_verify(s);
00280
00281     ASSERT(s->owner == current_process);
00282
00283     /*
00284      * Decrement nesting count and check if the semaphore
00285      * has been fully unlocked.
00286      */
00287     if (--s->nest_count == 0)
00288     {
00289         /* Give semaphore to the first applicant, if any */
00290         if (UNLIKELY((proc = (Process *)list_remHead(&s->wait_queue))))
00291         {
00292             /* Undo the effects of priority inheritance, if enabled */
00293             pri_inheritUnblock(s, proc);
00294
00295             s->nest_count = 1;
00296             s->owner = proc;
00297         } else {
00298             /* Disown semaphore */
00299             s->owner = NULL;
00300         }
00301     }
00302     proc_permit();
00303
00304     if (proc)
00305         ATOMIC(proc_wakeup(proc));
00306 }