sem.c

Go to the documentation of this file.

#include "sem.h"
#include <cfg/debug.h>

#include <cpu/irq.h> // ASSERT_IRQ_DISABLED()

#include <kern/proc.h>
#include <kern/proc_p.h>
#include <kern/signal.h>

INLINE void sem_verify(struct Semaphore *s)
{
    (void)s;
    ASSERT(s);
    LIST_ASSERT_VALID(&s->wait_queue);
    ASSERT(s->nest_count >= 0);
    ASSERT(s->nest_count < 128);   // heuristic max
}

#if CONFIG_KERN_PRI && CONFIG_KERN_PRI_INHERIT

#define proc_updatePri(proc) (proc_setPri(proc, (proc)->orig_pri))


INLINE void pri_inheritBlock(Semaphore *s)
{
    Process *owner = s->owner;

    /*
     * Enqueue the blocking process in the owner's inheritance
     * list. Notice that such process might have inherited its
     * current priority from someone else.
     */
    current_process->inh_link.pri = __prio_proc(current_process);
    LIST_ENQUEUE(&owner->inh_list, &current_process->inh_link);
    current_process->inh_blocked_by = s;

    /*
     * As long as a process has the power of boosting the priority
     * of its lock owner...
     */
    while (current_process->inh_link.pri > prio_proc(owner)) {
        Process *p = owner;

         /* Boost the priority of the owner */
        proc_updatePri(p);

        /* If the owner is not blocked, we're done */
        if (!p->inh_blocked_by)
            break;

        /*
         * Otherwise update the position of the owner
         * (which is `p' at each round!) in the inheritance
         * list it lies in and set up `owner' for the
         * next round.
         */
        REMOVE(&p->inh_link.link);
        p->inh_link.pri = prio_proc(p);
        owner = p->inh_blocked_by->owner;
        LIST_ENQUEUE(&owner->inh_list, &p->inh_link);
    }
}


INLINE void pri_inheritUnblock(Semaphore *s, Process *proc)
{
    Process *owner = s->owner;
    Node *n, *temp;
    Process *p;

    /*
     * This process has nothing more to do on a priority
     * inheritance list.
     */
    REMOVE(&proc->inh_link.link);
    proc->inh_blocked_by = NULL;

    /*
     * Each process in the former owner's priority inheritance
     * list that is blocked on 's' needs to be removed from
     * there and added to the priority inheritance list of
     * this process, since it's going to be the new owner for
     * that semaphore.
     */
    FOREACH_NODE_SAFE(n, temp, &owner->inh_list) {
        p = containerof(n, Process, inh_link.link);
        /* Ensures only the processes blocked on 's' are affected! */
        if (p->inh_blocked_by == s) {
            REMOVE(&p->inh_link.link);
            LIST_ENQUEUE(&proc->inh_list, &p->inh_link);

            /* And again, update the priority of the new owner */
            if (p->inh_link.pri > prio_proc(proc))
                proc_updatePri(proc);
        }
    }

    proc_updatePri(owner);
}
#else
INLINE void pri_inheritBlock(UNUSED_ARG(Semaphore *, s))
{
}

INLINE void pri_inheritUnblock(UNUSED_ARG(Semaphore *, s), UNUSED_ARG(Process *, proc))
{
}
#endif /* CONFIG_KERN_PRI_INHERIT */


void sem_init(struct Semaphore *s)
{
    LIST_INIT(&s->wait_queue);
    s->owner = NULL;
    s->nest_count = 0;
}


bool sem_attempt(struct Semaphore *s)
{
    bool result = false;

    proc_forbid();
    sem_verify(s);
    if ((!s->owner) || (s->owner == current_process))
    {
        s->owner = current_process;
        s->nest_count++;
        result = true;
    }
    proc_permit();

    return result;
}


void sem_obtain(struct Semaphore *s)
{
    proc_forbid();
    sem_verify(s);

    /* Is the semaphore already locked by another process? */
    if (UNLIKELY(s->owner && (s->owner != current_process)))
    {
        /* Append calling process to the wait queue */
        ADDTAIL(&s->wait_queue, (Node *)current_process);

        /* Trigger priority inheritance logic, if enabled */
        pri_inheritBlock(s);

        /*
         * We will wake up only when the current owner calls
         * sem_release(). Then, the semaphore will already
         * be locked for us.
         */
        proc_permit();
        proc_switch();
    }
    else
    {
        ASSERT(LIST_EMPTY(&s->wait_queue));

        /* The semaphore was free: lock it */
        s->owner = current_process;
        s->nest_count++;
        proc_permit();
    }
}


void sem_release(struct Semaphore *s)
{
    Process *proc = NULL;

    proc_forbid();
    sem_verify(s);

    ASSERT(s->owner == current_process);

    /*
     * Decrement nesting count and check if the semaphore
     * has been fully unlocked.
     */
    if (--s->nest_count == 0)
    {
        /* Give semaphore to the first applicant, if any */
        if (UNLIKELY((proc = (Process *)list_remHead(&s->wait_queue))))
        {
            /* Undo the effects of priority inheritance, if enabled */
            pri_inheritUnblock(s, proc);

            s->nest_count = 1;
            s->owner = proc;
        } else {
            /* Disown semaphore */
            s->owner = NULL;
        }
    }
    proc_permit();

    if (proc)
        ATOMIC(proc_wakeup(proc));
}