protothread_lock.h

/**************************************************************/
/* PROTOTHREAD_LOCK.H */
/* https://github.com/LarryRuane/protothread */
/* Copyright (c) 2008-present Larry Ruane */
/* Distributed under the MIT software license, see the accompanying */
/* file LICENSE or https://opensource.org/licenses/MIT. */
/* SPDX-License-Identifier: MIT */
/* Reader-writer (shared-exclusive) locks */
/**************************************************************/
#ifndef PROTOTHREAD_LOCK_H
#define PROTOTHREAD_LOCK_H

#include "protothread.h"

/* Reader-writer lock. The public API; pt_i_ names are internal.
 *   pt_lock_init(lock)                        initialize an unheld lock
 *   pt_lock_acquire_read(c, lock_env, lock)   block for shared (read) access
 *   pt_lock_acquire_write(c, lock_env, lock)  block for exclusive access
 *   pt_lock_release_read(lock_env, lock)      release; never blocks
 *   pt_lock_release_write(lock_env, lock)     release; never blocks
 *   pt_lock_cancel(lock_env, lock)            forget a request; true if known
 *   pt_lock_t, pt_lock_env_t                  the lock, and one env per waiter
 */

typedef enum {
    PT_I_LOCK_IDLE,             /* zeroed or released: lock has no record */
    PT_I_LOCK_READ,
    PT_I_LOCK_WRITE,
    PT_I_LOCK_READING,
    PT_I_LOCK_WRITING,
} pt_i_lock_state_t ;

/* per-thread */
typedef struct pt_lock_env_s {
    pt_func_t pt_func ;
    pt_i_lock_state_t state ;
    struct pt_lock_env_s *next ;
} pt_lock_env_t ;

/* per lock; waiting is a circular FIFO that points to the NEWEST waiter,
 * so waiting->next is the oldest -- the same convention protothread.h uses
 * for its run and wait lists. Requests are granted in arrival order, so a
 * steady stream of readers cannot starve a waiting writer.
 *
 * Before pt_kill()ing or freeing a protothread that might be using a lock,
 * call pt_lock_cancel(): otherwise its request stays in this queue and is
 * eventually granted to a thread that can't release it.
 */
typedef struct pt_lock_s {
    unsigned int nreaders ;             /* current readers */
    unsigned int nwriters ;             /* current writers, 0 or 1 */
    pt_lock_env_t *waiting ;            /* newest waiter's environment */
} pt_lock_t ;

static inline void
pt_lock_init(pt_lock_t *lock)
{
    lock->nreaders = 0 ;
    lock->nwriters = 0 ;
    lock->waiting = NULL ;
}

/* the oldest waiter, or NULL */
static inline pt_lock_env_t *
pt_i_lock_oldest(pt_lock_t const *lock)
{
    return lock->waiting ? lock->waiting->next : NULL ;
}

/* append to the tail of the FIFO */
static inline void
pt_i_lock_enqueue(pt_lock_t *lock, pt_lock_env_t *c)
{
    if (lock->waiting) {
        c->next = lock->waiting->next ;
        lock->waiting->next = c ;
    } else {
        c->next = c ;
    }
    lock->waiting = c ;
}

/* remove a particular waiter; return TRUE if it was queued */
static inline bool_t
pt_i_lock_unqueue(pt_lock_t *lock, pt_lock_env_t *c)
{
    pt_lock_env_t *prev = lock->waiting ;

    if (prev == NULL) {
        return false ;
    }
    do {
        if (prev->next == c) {
            prev->next = c->next ;
            if (c == lock->waiting) {
                /* the newest is leaving; the one before it becomes newest */
                lock->waiting = (c == prev) ? NULL : prev ;
            }
            c->next = NULL ;
            return true ;
        }
        prev = prev->next ;
    } while (prev != lock->waiting) ;
    return false ;
}

/* remove the oldest waiter (which must exist) */
static inline void
pt_i_lock_dequeue(pt_lock_t *lock)
{
    pt_lock_env_t * const oldest = lock->waiting->next ;
    if (oldest == lock->waiting) {
        lock->waiting = NULL ;
    } else {
        lock->waiting->next = oldest->next ;
    }
}

/* start as many requests as possible, in arrival order
 */
static inline void
pt_i_lock_update(pt_lock_t *lock)
{
    pt_lock_env_t *w = pt_i_lock_oldest(lock) ;

    if (w == NULL) {
        /* nothing to do */
        return ;
    }

    switch (w->state) {
    case PT_I_LOCK_READ:
        if (lock->nwriters) {
            pt_assert(lock->nwriters == 1) ;
            return ;
        }
        /* start the first and every consecutive additional reader */
        while ((w = pt_i_lock_oldest(lock)) != NULL
                && w->state == PT_I_LOCK_READ) {
            lock->nreaders ++ ;
            pt_i_lock_dequeue(lock) ;
            w->state = PT_I_LOCK_READING ;
            pt_broadcast(pt_get_pt(w), w) ;
        }
        break ;
    case PT_I_LOCK_WRITE:
        if (lock->nreaders || lock->nwriters) {
            break ;
        }
        lock->nwriters ++ ;
        pt_i_lock_dequeue(lock) ;
        w->state = PT_I_LOCK_WRITING ;
        pt_broadcast(pt_get_pt(w), w) ;
        break ;
    case PT_I_LOCK_IDLE:
    case PT_I_LOCK_READING:
    case PT_I_LOCK_WRITING:
        /* this request is not waiting for anything! */
        pt_assert(0) ;
        break ;
    }
}

static inline pt_t
pt_i_lock_acquire_read(pt_lock_env_t *c, pt_lock_t *lock)
{
    pt_resume(c) ;
    c->state = PT_I_LOCK_READ ;
    pt_i_lock_enqueue(lock, c) ;
    pt_i_lock_update(lock) ;
    while (c->state == PT_I_LOCK_READ) {
        pt_wait(c, c) ;
    }
    pt_assert(c->state == PT_I_LOCK_READING) ;
    return PT_DONE ;
}
#define pt_lock_acquire_read(c, lock_env, lock) \
    pt_call(c, pt_i_lock_acquire_read, lock_env, lock)

static inline pt_t
pt_i_lock_acquire_write(pt_lock_env_t *c, pt_lock_t *lock)
{
    pt_resume(c) ;
    c->state = PT_I_LOCK_WRITE ;
    pt_i_lock_enqueue(lock, c) ;
    pt_i_lock_update(lock) ;
    while (c->state == PT_I_LOCK_WRITE) {
        pt_wait(c, c) ;
    }
    pt_assert(c->state == PT_I_LOCK_WRITING) ;
    return PT_DONE ;
}
#define pt_lock_acquire_write(c, lock_env, lock)\
    pt_call(c, pt_i_lock_acquire_write, lock_env, lock)

/* guaranteed not to break context */
static inline void
pt_lock_release_read(pt_lock_env_t *c, pt_lock_t *lock)
{
    (void)c ;   /* only referenced by pt_assert() */
    pt_assert(c->state == PT_I_LOCK_READING) ;
    pt_assert(!lock->nwriters) ;
    pt_assert(lock->nreaders) ;
    c->state = PT_I_LOCK_IDLE ;
    lock->nreaders -- ;
    pt_i_lock_update(lock) ;
}

static inline void
pt_lock_release_write(pt_lock_env_t *c, pt_lock_t *lock)
{
    (void)c ;   /* only referenced by pt_assert() */
    pt_assert(c->state == PT_I_LOCK_WRITING) ;
    pt_assert(!lock->nreaders) ;
    pt_assert(lock->nwriters == 1) ;
    c->state = PT_I_LOCK_IDLE ;
    lock->nwriters -- ;
    pt_i_lock_update(lock) ;
}

/* Take a request out of the lock, whether it is still queued or has already
 * been granted, and let whatever that unblocks proceed. The protothread is
 * NOT woken, so this is for use before pt_kill()ing or freeing one that might
 * be using the lock, as pt_timer_cancel() is for one that might be sleeping.
 * Returns TRUE if the lock still knew about the request. The lock_env must
 * have been zeroed or used with this lock; never blocks.
 */
static inline bool_t
pt_lock_cancel(pt_lock_env_t *c, pt_lock_t *lock)
{
    bool_t found ;

    switch (c->state) {
    case PT_I_LOCK_READING:
        pt_assert(lock->nreaders) ;
        lock->nreaders -- ;
        found = true ;
        break ;
    case PT_I_LOCK_WRITING:
        pt_assert(lock->nwriters == 1) ;
        lock->nwriters -- ;
        found = true ;
        break ;
    default:
        found = pt_i_lock_unqueue(lock, c) ;
        break ;
    }
    c->state = PT_I_LOCK_IDLE ;
    if (found) {
        pt_i_lock_update(lock) ;
    }
    return found ;
}

/* TODO: "try" routines (cannot block, return bool_t)
 *
 * An upgrade needs no routine of its own: release the read lock, acquire the
 * write lock, and pt_call_waited() says whether that blocked. If it didn't,
 * nothing else ran and the upgrade was atomic; see doc/lock.md.
 */

#endif /* PROTOTHREAD_LOCK_H */