mpsc_lockfree.h

Go to the documentation of this file.

/*
 * Copyright (c) 2010-2011 Dmitry Vyukov
 * Copyright (c) 2023 Intel Corporation
 *
 * SPDX-License-Identifier: Apache-2.0
 */
 
#ifndef ZEPHYR_SYS_MPSC_LOCKFREE_H_
#define ZEPHYR_SYS_MPSC_LOCKFREE_H_
 
#include <stdint.h>
#include <stdbool.h>
#include <zephyr/sys/atomic.h>
#include <zephyr/kernel.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
/*
 * On single core systems atomics are unnecessary
 * and cause a lot of unnecessary cache invalidation
 *
 * Using volatile to at least ensure memory is read/written
 * by the compiler generated op codes is enough.
 *
 * On SMP atomics *must* be used to ensure the pointers
 * are updated in the correct order.
 */
#if defined(CONFIG_SMP)
 
typedef atomic_ptr_t mpsc_ptr_t;
 
#define mpsc_ptr_get(ptr)          atomic_ptr_get(&(ptr))
#define mpsc_ptr_set(ptr, val)     atomic_ptr_set(&(ptr), val)
#define mpsc_ptr_set_get(ptr, val) atomic_ptr_set(&(ptr), val)
 
#else /* defined(CONFIG_SMP) */
 
typedef struct mpsc_node *mpsc_ptr_t;
 
#define mpsc_ptr_get(ptr)      ptr
#define mpsc_ptr_set(ptr, val) ptr = val
#define mpsc_ptr_set_get(ptr, val)                                                                 \
        ({                                                                                         \
                mpsc_ptr_t tmp = ptr;                                                              \
                ptr = val;                                                                         \
                tmp;                                                                               \
        })
 
#endif /* defined(CONFIG_SMP) */
 
struct mpsc_node {
        mpsc_ptr_t next;
};
 
struct mpsc {
        mpsc_ptr_t head;
        struct mpsc_node *tail;
        struct mpsc_node stub;
};
 
#define MPSC_INIT(symbol)                                                                          \
        {                                                                                          \
                .head = (struct mpsc_node *)&symbol.stub,                                          \
                .tail = (struct mpsc_node *)&symbol.stub,                                          \
                .stub = {                                                                          \
                        .next = NULL,                                                              \
                },                                                                                 \
        }
 
static inline void mpsc_init(struct mpsc *q)
{
        mpsc_ptr_set(q->head, &q->stub);
        q->tail = &q->stub;
        mpsc_ptr_set(q->stub.next, NULL);
}
 
static ALWAYS_INLINE void mpsc_push(struct mpsc *q, struct mpsc_node *n)
{
        struct mpsc_node *prev;
        int key;
 
        mpsc_ptr_set(n->next, NULL);
 
        key = arch_irq_lock();
        prev = (struct mpsc_node *)mpsc_ptr_set_get(q->head, n);
        mpsc_ptr_set(prev->next, n);
        arch_irq_unlock(key);
}
 
static inline struct mpsc_node *mpsc_pop(struct mpsc *q)
{
        struct mpsc_node *head;
        struct mpsc_node *tail = q->tail;
        struct mpsc_node *next = (struct mpsc_node *)mpsc_ptr_get(tail->next);
 
        /* Skip over the stub/sentinel */
        if (tail == &q->stub) {
                if (next == NULL) {
                        return NULL;
                }
 
                q->tail = next;
                tail = next;
                next = (struct mpsc_node *)mpsc_ptr_get(next->next);
        }
 
        /* If next is non-NULL then a valid node is found, return it */
        if (next != NULL) {
                q->tail = next;
                return tail;
        }
 
        head = (struct mpsc_node *)mpsc_ptr_get(q->head);
 
        /* If next is NULL, and the tail != HEAD then the queue has pending
         * updates that can't yet be accessed.
         */
        if (tail != head) {
                return NULL;
        }
 
        mpsc_push(q, &q->stub);
 
        next = (struct mpsc_node *)mpsc_ptr_get(tail->next);
 
        if (next != NULL) {
                q->tail = next;
                return tail;
        }
 
        return NULL;
}
 
#ifdef __cplusplus
}
#endif
 
#endif /* ZEPHYR_SYS_MPSC_LOCKFREE_H_ */